C#实现斐波那契数列的几种方法整理

什么是斐波那契数列

斐波那契数列是一个非常著名的数列，其前两项是0和1，后续项是前两项之和，即：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

方法一：递归

递归是一种自上而下的方式解决问题，可以很自然地实现斐波那契数列。

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

这段代码实现了一个递归函数，接收整数参数 n，返回对应的斐波那契数列值。如果 n <= 1，直接返回 n；否则，递归求解 Fibonacci(n - 1) 和 Fibonacci(n - 2) 的值并相加。

但是，递归函数的效率非常低，因为会存在大量重复计算。例如，当计算 Fibonacci(5) 时，需要计算 Fibonacci(4) 和 Fibonacci(3)，而计算 Fibonacci(4) 时又需要计算 Fibonacci(3) 和 Fibonacci(2)，这里就出现了重复计算的问题。

方法二：迭代

迭代是一种自下而上的方式解决问题，可以避免递归中的大量重复计算。

public static int Fibonacci(int n) 
{ 
    if (n <= 1) return n; 

    int prev = 0, cur = 1;
    for (int i = 2; i <= n; ++i) 
    { 
        int sum = prev + cur; 
        prev = cur; 
        cur = sum; 
    } 
    return cur;
} 

这段代码实现了一个迭代函数，接收整数参数 n，返回对应的斐波那契数列值。如果 n <= 1，直接返回 n；否则，使用 for 循环计算前两个数的和，并更新 prev 和 cur，最后返回 cur 就是斐波那契数列的值。

方法三：矩阵快速幂

矩阵快速幂是一种高效并且通用的解决方案，可以用于求解数列的某一项。

public static int Fibonacci(int n) 
{ 
    if (n <= 1) return n; 

    int[,] matrix = new int[2, 2] { {1, 1}, {1, 0} };
    matrix = MatrixPow(matrix, n - 1); 

    return matrix[0, 0];
} 

private static int[,] MatrixPow(int[,] a, int n)
{
    int[,] ret = new int[,] { {1, 0}, {0, 1} };
    while (n > 0)
    {
        if ((n & 1) == 1) 
            ret = Multiply(ret, a);
        n >>= 1;
        a = Multiply(a, a);
    }
    return ret;
}

private static int[,] Multiply(int[,] a, int[,] b)
{
    int[,] c = new int[,] { {0, 0}, {0, 0} };
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                c[i, j] += a[i, k] * b[k, j];
    return c;
}

这段代码实现了一个矩阵快速幂函数，接收 2x2 的矩阵 a 和正整数 n，返回 a 的 n 次幂。其中，Multiply 函数用于计算两个矩阵相乘的结果。

在 Fibonacci 函数中，使用 2x2 的矩阵实现斐波那契数列。当 n <= 1 时，直接返回 n；否则，通过调用 MatrixPow 函数计算矩阵的 n - 1 次幂，并返回结果矩阵的左上角元素。

示例

接下来，我们用三种方法分别计算斐波那契数列的第 10 项，并比较它们的效率。

int n = 10;
int result;

// 递归
var watch = Stopwatch.StartNew();
result = FibonacciRecursive(n);
watch.Stop();
Console.WriteLine($"Fibonacci({n}) = {result}; Recursive: {watch.Elapsed.TotalMilliseconds}ms");

// 迭代
watch = Stopwatch.StartNew();
result = FibonacciIterative(n);
watch.Stop();
Console.WriteLine($"Fibonacci({n}) = {result}; Iterative: {watch.Elapsed.TotalMilliseconds}ms");

// 矩阵快速幂
watch = Stopwatch.StartNew();
result = FibonacciMatrix(n);
watch.Stop();
Console.WriteLine($"Fibonacci({n}) = {result}; Matrix: {watch.Elapsed.TotalMilliseconds}ms");

以上代码依次计算斐波那契数列的第 10 项，输出计算结果和执行时间。通过比较这三种方法的执行时间，可以发现递归函数是最慢的，矩阵快速幂是最快的，迭代函数位于它们之间。

总结

斐波那契数列有很多种计算方法，本文介绍了递归、迭代和矩阵快速幂三种实现方法，并且给出了相应的示例。在实际应用时，应该选择合适的算法以提高计算效率。