คำนวณกำลังด้วย Recursion ใน C#

การคำนวณกำลังด้วย Recursion (การเรียกซ้ำ) ใน C#

Recursive Function เรียกตัวเองจนถึง Base Case แล้วคืนค่ากลับมาทีละขั้น

หลักการ Recursion สำหรับ Power

power(n, p) = n * power(n, p-1)  // Recursive Case
power(n, 0) = 1                    // Base Case

ตัวอย่างโค้ด

using System;

public class Demo
{
    public static void Main(string[] args)
    {
        int n = 5;  // Base
        int p = 2;  // Exponent
        long result = Power(n, p);
        Console.WriteLine($"{n}^{p} = {result}"); // 25
    }
    
    static long Power(int n, int p)
    {
        if (p != 0)
            return n * Power(n, p - 1); // Recursive Call
        return 1; // Base Case
    }
}

ผลลัพธ์

5^2 = 25

การทำงานทีละขั้น (Trace)

Power(5, 2)
  = 5 * Power(5, 1)
  = 5 * (5 * Power(5, 0))
  = 5 * (5 * 1)
  = 25

ปรับปรุง: Tail Recursion (ไม่ได้ Optimize ใน C# ปัจจุบัน)

static long PowerTail(int n, int p, long acc = 1)
{
    if (p == 0) return acc;
    return PowerTail(n, p - 1, acc * n); // Tail Call
}

Iterative Version (แนะนำ - ไม่มี Stack Overflow Risk)

static long PowerIterative(int n, int p)
{
    long result = 1;
    for (int i = 0; i < p; i++)
        result *= n;
    return result;
}

// หรือ Binary Exponentiation (O(log n))
static long PowerFast(long n, long p)
{
    long result = 1;
    while (p > 0)
    {
        if ((p & 1) == 1) result *= n;
        n *= n;
        p >>= 1;
    }
    return result;
}

ข้อจำกัดของ Recursion ใน C#

• Stack Overflow หาก Recursion Depth มากเกินไป (~10,000-100,000 ขึ้นอยู่กับ Stack Size)
• ไม่มี Tail Call Optimization (TCO) ใน CLR ปัจจุบัน (F# มี)
• ช้ากว่า Iterative เนื่องจาก Overhead ของ Function Call

เมื่อไหร่ควรใช้ Recursion

• Tree/Graph Traversal (DFS)
• Divide & Conquer (QuickSort, MergeSort)
• Backtracking (N-Queens, Maze)
• Depth เล็กและแน่นอน (เช่น Factorial, Fibonacci, Power)