Tìm số Fibonacci thứ n bằng đệ quy trong C#

Dãy Fibonacci: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Đệ quy đơn giản nhưng kém hiệu quả (O(2^n)) do tính toán trùng lặp.

Đệ quy đơn giản (chỉ để học)

using System;

class Program
{
    static int Fibonacci(int n)
    {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    
    static void Main()
    {
        int n = 7;
        Console.WriteLine($"F({n}) = {Fibonacci(n)}");
    }
}

Kết quả đầu ra

F(7) = 13

Phiên bản tối ưu: Memoization (Đệ quy + Cache)

using System;
using System.Collections.Generic;

class Program
{
    static Dictionary _cache = new Dictionary();
    
    static long FibonacciMemo(int n)
    {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (_cache.TryGetValue(n, out long cached)) return cached;
        
        long result = FibonacciMemo(n - 1) + FibonacciMemo(n - 2);
        _cache[n] = result;
        return result;
    }
    
    static void Main()
    {
        Console.WriteLine($"F(50) = {FibonacciMemo(50)}"); // Nhanh chóng
    }
}

Phiên bản lặp (Iterative - O(n), O(1) memory) - Khuyên dùng

static long FibonacciIterative(int n)
{
    if (n <= 0) return 0;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++)
    {
        long temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Lưu ý: Đệ quy đơn giản chỉ dùng cho n nhỏ (< 40). Dùng iterative hoặc matrix exponentiation (O(log n)) cho production.