C#斐波那契数列的三种实现：递归、自底向上非递归与自顶向下缓存

斐波那契数列的定义与算法选择

斐波那契数列（Fibonacci sequence）定义为：
当 n=0 或 n=1 时，F(n)=1；
当 n>1 时，F(n)=F(n-1)+F(n-2)。

在实际项目中，简单的递归往往因为重复计算子问题导致指数级时间复杂度。因此，根据输入规模的大小，选择合适的算法策略至关重要。下面将展示如何在同一个 Function 类中封装这三种策略。

第1步：准备环境与控制台入口

首先创建一个名为 Fibonacci 的控制台项目。主程序负责接收用户输入的整数参数，并实例化计算方法类来执行具体的数值获取操作。

using System;
namespace Fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Would you like to know which Fibonacci Numbers：");
            int number = Convert.ToInt32(Console.ReadLine());
            Function obj = new Function();
            Function obj2 = new Function(number);

            // 调用不同的实现方法
            Console.Write("The {0} Fibonacci number is：{1}", number, obj.Fibonacci(number));
            Console.Write("The {0} Fibonacci number is：{1}", number, obj2.BottomUpNotRecursion(number));
            Console.Write("The {0} Fibonacci number is：{1}", number, obj2.TopDownRecursion(number));
            Console.ReadKey();
        }
    }
}

第2步：使用纯递归实现 (Fibonacci)

目的：通过最简逻辑直观展示数列的数学定义。
原理：直接调用自身来计算前两项的和。
注意：随着数字增大，此方法性能会急剧下降，不适合生产环境的大数计算。

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

第3步：自底向上非递归算法 (BottomUpNotRecursion)

目的：消除递归调用栈开销，利用动态规划思想提升运行速度。
操作：在构造函数中初始化一个长度足够的整型数组 array。从索引 2 开始循环累加，直接覆盖数组元素，最终返回最后一项。

private int[] array;

public Function(int length)
{
    if (length > 0)
    {
        array = new int[length + 1];
        array[0] = 1;
        array[1] = 1;
    }
}

public int BottomUpNotRecursion(int number)
{
    int copynumber = 0;
    if (number < 2)
    {
        copynumber = 1;
    }
    else
    {
        int one = array[0];
        int two = array[1];
        for (int i = 2; i < array.Length; i++)
        {
            array[i] = one + two;
            one = two;
            two = array[i];
            copynumber = array[i];
        }
    }
    return copynumber;
}

第4步：自顶向下递归与缓存结合 (TopDownRecursion)

目的：保留递归的代码简洁性，同时通过预先分配的数组作为“备忘录”避免重复计算。
操作：如果目标值大于2，先递归调用 TopDownRecursion(number - 1)，强制填满前面的数值后，再通过 array[number] = array[number - 1] + array[number - 2] 得出当前结果。

public int TopDownRecursion(int number)
{
    if (number <= 2)
    {
        if (number == 0) return array[0];
        if (number == 1) return array[1];
        if (number == 2) return array[2] = array[0] + array[1];
    }
    else
    {
        TopDownRecursion(number - 1);
        array[number] = array[number - 1] + array[number - 2];
    }
    return array[number];
}

完成判断与验证

程序运行后，控制台会按照顺序输出三次计算结果。若三次输出的数值一致，说明三种算法在当前测试环境下均正确执行。由于使用了相同的 array 数据结构，非递归和带缓存的递归都能保证 O(n) 的时间复杂度表现。

以上就是C#斐波那契数列实现的详细内容，更多关于C#算法优化的资料请关注本站其它相关文章！