本文共 1276 字，大约阅读时间需要 4 分钟。

引言

递归函数(输入){    if(终止条件)        return 终止条件下的解    输入=子问题    return 递归函数(输入)}

long long fib(int n){    if (n == 0) return 0;     else if (n == 1) return 1; // 前两个数为终止情况     else return fib(n-1) + fib(n-2); // 分解为子问题}int main(){    int n;    while(1)    {        scanf("%d",&n);        printf("The %dth number in the Fibonacci sequence is %lld.\n",n,fib(n));    }    return 0;}

演示GIF：

斐波那契数列高效递归方法

文字太累，直接上图。

你会发现fib(0)重复计算了2次，fib(1)重复计算了3次，fib(2)重复计算了2次，导致这样问题的出现是因为我们并没有高效地将原问题分解为规模较小的子问题。

我们原本是从后往前分解问题，那么为什么不尝试一下从前往后分解问题呢？

当我们人脑计算第5项时，首先计算第3项=第1项+第2项，之后计算第4项，最后得到第5项。

那么我们就可以修改代码为：

long long fib(int n,int n0,int n1){    if (n == 0) return n0;     else if (n == 1) return n1;// 前两个数为终止情况     else return fib(n-1,n1,n0+n1); // 分解为子问题}int main(){    int n;    while(1)    {	scanf("%d",&n);        printf("The %dth item in the Fibonacci sequence is %lld.\n",n,fib(n,0,1));    }    return 0;}

转载地址：https://blog.csdn.net/huzhiyuan0000000/article/details/73896491 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！