หาค่า Fibonacci ลำดับที่ n ด้วย Recursion ใน C#

ภาพรวม

Fibonacci sequence: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) ใช้ recursion คำนวณค่าลำดับที่ n

โค้ดตัวอย่าง (Naive Recursion - O(2^n))

using System;

public class Demo {
    public static void Main() {
        int n = 7;
        int result = Fibonacci(n);
        Console.WriteLine($"{n}th Fibonacci number = {result}"); // 13
    }

    public static int Fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

ผลลัพธ์

7th Fibonacci number = 13

ปัญหาของ Naive Recursion

• Time Complexity: O(2^n) - ช้ามากสำหรับ n > 40
• คำนวณซ้ำซ้อนมาก (overlapping subproblems)
• Stack Overflow สำหรับ n ใหญ่

วิธีที่ดีกว่า: Memoization (Top-Down DP)

using System;
using System.Collections.Generic;

public class Demo {
    static Dictionary<int, long> _memo = new Dictionary<int, long>();

    public static void Main() {
        int n = 50;
        Console.WriteLine($"F({n}) = {Fibonacci(n)}"); // 12586269025
    }

    static long Fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (_memo.ContainsKey(n)) return _memo[n];

        long result = Fibonacci(n - 1) + Fibonacci(n - 2);
        _memo[n] = result;
        return result;
    }
}

วิธีที่ดีที่สุด: Iterative (Bottom-Up) O(n) time, O(1) space

static long FibonacciIterative(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

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

วิธี Math: Binet's Formula O(1)

static long FibonacciBinet(int n) {
    double phi = (1 + Math.Sqrt(5)) / 2;
    return (long)Math.Round(Math.Pow(phi, n) / Math.Sqrt(5));
}
// ใช้ได้จนถึง n ≈ 70 (precision limit ของ double)

สรุปประสิทธิภาพ