คูณเลขสองจำนวนด้วย Recursion ใน C#

ภาพรวม

คูณ a × b โดยการบวก a ซ้ำ b ครั้ง ใช้ recursion

โค้ดตัวอย่าง (Naive Recursion)

using System;

class Calculation {
    public static void Main() {
        int val1 = 10, val2 = 20;
        Demo d = new Demo();
        int res = d.Product(val1, val2);
        Console.WriteLine($"{val1} x {val2} = {res}"); // 200
    }
}

class Demo {
    public int Product(int val1, int val2) {
        // Optimization: swap to minimize recursion depth
        if (val1 < val2) return Product(val2, val1);

        if (val2 == 0) return 0;
        return val1 + Product(val1, val2 - 1);
    }
}

ผลลัพธ์

10 x 20 = 200

ปัญหาของ Naive Recursion

• Stack depth = val2 (อาจ StackOverflow ถ้า val2 ใหญ่)
• Time O(val2) - ช้า

วิธีที่ดีกว่า: Russian Peasant Multiplication (O(log n))

static int Multiply(int a, int b) {
    int result = 0;
    while (b > 0) {
        if ((b & 1) != 0) result += a;
        a <<= 1; // a *= 2
        b >>= 1; // b /= 2
    }
    return result;
}

วิธี Recursive แบบ Optimized (Divide & Conquer)

static int MultiplyRecursive(int a, int b) {
    if (b == 0) return 0;
    if (b == 1) return a;

    int half = MultiplyRecursive(a, b / 2);
    if (b % 2 == 0) return half + half;
    return half + half + a;
}

รองรับตัวเลขลบ

static int Multiply(int a, int b) {
    bool negative = (a < 0) ^ (b < 0);
    a = Math.Abs(a);
    b = Math.Abs(b);

    int result = MultiplyPositive(a, b);
    return negative ? -result : result;
}

static int MultiplyPositive(int a, int b) {
    if (b == 0) return 0;
    int half = MultiplyPositive(a, b / 2);
    if (b % 2 == 0) return half + half;
    return half + half + a;
}

สรุป