斐波那契数列：递归、记忆和最优方法

斐波那契数列是一种流行的数学序列，出现在从计算机科学到自然界的各个领域。该序列以两个数字 0 和 1 开始，每个后续数字都是前两个数字的总和。

一、什么是斐波那契数列？

F(0) = 0，F(1) = 1，
F(n) = F(n−1) + F(n−2) 其中 n ≥ 2。

在本文中，我们将探讨在 C# 中计算斐波那契数列的三种不同方法：使用递归、记忆和最佳编程方法。

二、使用递归的斐波那契数列

递归方法是计算斐波那契数列的一种简单且直观的方法。然而，正如我们将在复杂性分析中看到的那样，它并不是最有效的方法。

public static int FibonacciRecursive(int n)
{
    if (n <= 1) return n; // 基础情况
    return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2); // 子问题
}

输出

对每个 n 值递归调用函数 FibonacciRecursive，通过计算 n-1 和 n-2 的值来减少问题规模。对于较小的 n 值，这种方法效果很好，但对于较大的值，递归调用的次数会呈指数增长。

• 时间复杂度：O(2^n) – 每个函数调用都会分支为两个额外调用，导致调用次数呈指数增长。
• 空间复杂度：O(n) – 递归堆栈的最大深度为 n，它定义了空间复杂度。

三、使用记忆法的斐波那契数列

记忆化是一种通过存储先前计算的结果来优化递归解决方案的技术。这避免了基本递归方法中出现的冗余计算。

public static int FibonacciMemoization(int n, Dictionary<int, int> memo = null)
{
    if (memo == null) memo = new Dictionary<int, int>(); // 用于存储先前的结果以避免冗余递归调用
    if (n <= 1) return n; // 基础情况
    if (!memo.ContainsKey(n)) // 检查结果是否已经存在
        memo[n] = FibonacciMemoization(n - 1, memo) + FibonacciMemoization(n - 2, memo); // 子问题
    return memo[n];
}

输出

在这种方法中，我们使用字典（或数组）来存储先前计算的斐波那契数。如果函数已经计算了 F(n)，它会从字典中检索结果，而不是进行递归调用。

• 时间复杂度：O(n) – 每个斐波那契数仅计算一次并存储，避免了指数调用。
• 空间复杂度：O(n) – 需要额外的空间来存储结果，加上递归深度。

四、使用最优方法计算斐波那契数列

在这种斐波那契方法中，我们只需要最后两个斐波那契值来计算下一个值，因此通过仅存储这两个值（而不是整个序列），我们在循环中迭代计算结果。这可将时间复杂度降低至 O(n)，并将空间复杂度降低至 O(1)。

public static int FibonacciOptimal(int n)
{
    if (n <= 1) return n;
    int prev1 = 0, prev2 = 1; // 用于存储最后两个结果的变量
    for (int i = 2; i <= n; i++)
    {
        int current = prev1 + prev2; // 计算当前的斐波那契数
        prev1 = prev2; // 更新 prev1 为 prev2
        prev2 = current; // 更新 prev2 为当前值
    }
    return prev2; // 返回最后的斐波那契数
}

输出

我们初始化两个变量，prev1和prev2，代表前两个斐波那契数。当我们从 2 迭代到 n 时，我们更新这两个变量来计算当前的斐波那契数。这种方法完全避免了递归并使用了恒定的空间。

• 时间复杂度：O(n) – 对该序列进行一次迭代，直到 n。
• 空间复杂度：O(1) – 只需要恒定量的空间，因为我们在任何给定时间只存储两个变量。

五、比较方法

让我们总结一下这三种方法的时间和空间复杂度。

六、完整代码

using System;
using System.Collections.Generic;

namespace FibonacciSeries
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = 10; // 计算第 n 个斐波那契数

            Console.WriteLine("Fibonacci number using recursion for n = " + n + ":");
            Console.Write(FibonacciRecursive(n) + " ");

            Console.WriteLine("\n\nFibonacci number using memoization for n = " + n + ":");
            Console.Write(FibonacciMemoization(n) + " ");

            Console.WriteLine("\n\nFibonacci number using the optimal approach for n = " + n + ":");
            Console.Write(FibonacciOptimal(n) + " ");
            Console.ReadLine();
        }

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

        public static int FibonacciMemoization(int n, Dictionary<int, int> memo = null)
        {
            if (memo == null) memo = new Dictionary<int, int>();
            if (n <= 1) return n;
            if (!memo.ContainsKey(n))
                memo[n] = FibonacciMemoization(n - 1, memo) + FibonacciMemoization(n - 2, memo);
            return memo[n];
        }

        public static int FibonacciOptimal(int n)
        {
            if (n <= 1) return n;
            int prev1 = 0, prev2 = 1;
            for (int i = 2; i <= n; i++)
            {
                int current = prev1 + prev2;
                prev1 = prev2;
                prev2 = current;
            }
            return prev2;
        }
    }
}

输出

根据上面的代码，你可以计算任意 n 值的斐波那契数列。