『C#』如何用递归计算斐波那契数列的第 100000 项?

本文最后更新于 2019年 5月 1号下午 6点 36分，并同步发布于 :

简书 —— 创作你的创作

CSDN —— 专业 IT 技术社区

www.tobinary.art —— 我的博客

斐波那契数列

声明 : 请不要使用本文的代码直接用于实际项目，本文的目的是以这个示例给读者提供一点编程上的思路

本文假设读者有对如下概念有所了解 :

如何用递归计算斐波那契数列的第 100000 项 ?
有的同学可能会说 : 那还不简单, 不到一分钟便写出了如下代码 :

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

或者 :

public static int Fibonacci(int n)
    => n <= 2
    ? 1
    : Fibonacci(n - 1) + Fibonacci(n - 2);

先测试一下斐波那契数列的第 10 项试试 :

再试试第 50 项 :

结果竟然是负数 ? 不过仔细一想, 是因为结果值超出了 int 类型的存储范围。而且用了 一分多钟 的时间！

第 100 项呢 :
emmmmmmm... ... 由于我生命有限, 就不测试这个了, 估计我睡完一觉了还没得出结果 orz

如果计算更大的项时, 很可能出现下面的情况 : (具体多大的项因电脑配置而异)

程序计算比较大的项时, 发生了 堆栈溢出 异常。

递归计算斐波那契数列时, 函数调用的次数是 指数级 增加的

在解决问题之前我们先看一下递归求斐波那契数列的函数调用情况 :

可以看到, 在计算结果时, 出现了很多重复计算
这也是为什么计算比较大的项时，用时非常长

将值缓存起来

那么应该如何改写上面写的函数呢？
我们可以通过把已经计算过的值存储在一个容器中，等下次需要计算时，直接从中取值。
这样可以大幅度的减少函数递归调用的次数

当然还有一个问题：
计算比较大的项时，值可能非常大，超出了所有C#内置的基本整数类型的最大存储范围。
所以我们需要使用 System.Numerics 命名空间下的大整数类型 : BigInteger, 这个类型可以存储任意大的整数。当然也可以自己手写一个大整数类型。至于怎么写一个大整数类型，不在本文的讨论范围。