Tính lũy thừa bằng đệ quy trong C#

Đệ quy tính lũy thừa: x^n = x * x^(n-1) với điều kiện dừng n == 0 trả về 1.

Ví dụ cơ bản

using System;

class Program
{
    static long Power(int baseNum, int exponent)
    {
        if (exponent == 0) return 1;
        if (exponent < 0) throw new ArgumentException("Số mũ phải >= 0");
        
        return baseNum * Power(baseNum, exponent - 1);
    }
    
    static void Main()
    {
        int n = 15, p = 2;
        long result = Power(n, p);
        Console.WriteLine($"{n}^{p} = {result}");
    }
}

Kết quả đầu ra

15^2 = 225

Phiên bản tối ưu: Exponentiation by Squaring (O(log n))

static long PowerFast(long baseNum, int exponent)
{
    if (exponent == 0) return 1;
    if (exponent < 0) throw new ArgumentException("Số mũ phải >= 0");
    
    long half = PowerFast(baseNum, exponent / 2);
    if (exponent % 2 == 0)
        return half * half;
    else
        return half * half * baseNum;
}

So sánh: Đệ quy đơn giản O(n), chia để trị O(log n). Cẩn tràn số với số lớn - dùng BigInteger (System.Numerics).