递归 Finbonacci 优化

Question

下面的代码是用来计算前 70 个斐波那契数列的。我有两个问题：

1) 为什么程序会随着 i 的每个连续值变得越来越慢？是不是调用大号函数导致内存占用大

2) 我可以使用什么技术或编码方案来加快程序在运行时的计算速度？

#include <iostream>

int fib(int n) {
  if (n == 1 || n == 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

void main() {
  for (int i = 1; i<70; i++)
    cout << " fib(" << i << ") = " << fib(i) << endl;
}

Answer 1

1) Why does the program get increasingly slower for each successive value of i?

只是函数的递归调用越多，执行时间越长

Is it because calling the function with high numbers causes heavy memory footprint.

不，没有过多的内存占用（通过昂贵的动态内存分配操作）。所有需要的内存都保存在堆栈中，堆栈已经为进程预先分配。

不过，您可能很容易运行将可用堆栈内存用完，以获得稍大的数字。

2)What technique or coding scheme could I use to speed up the programs calculations at run time?

递归可能不是解决该问题的最佳方法。此处已有更详细的答案：

Is there a better way (performance) calculate fibonacci than this one?

Answer 2

递归斐波那契计算具有指数级的复杂性，所以很快就变慢了。可以看分析here

为了更快地计算斐波那契甚至不要考虑使用递归！ 使用简单的循环，像这样：

#include <iostream>
#include <cassert>
#include <stdint.h>

uint64_t fib(uint64_t n)
{
    assert(n>0);
    uint64_t fprev = 1;
    uint64_t fprev2 = 0;
    while (--n>0)
    {
        uint64_t t = fprev2;
        fprev2 = fprev;
        fprev += t;

    }
    return fprev;
};

int main(int, char**)
{
    for(uint64_t i=1; i<70; i++)
    std::cout<<" fib("<<i<<") = "<<fib(i)<<std::endl;
    return 0;
}

如果您需要更快地计算它，您可以在程序启动时预先计算它们并保存到 table 以供进一步使用。

此外，Fibonacci 数列增长非常快（也像指数函数），因此请注意整数溢出。

Answer 3

要加快程序速度，您需要使用 memoisation 技术，这是 "Do not recalculate just store the answer and use it again when needed".

的一种非常奇特的表达方式

您正在使用递归来计算答案，并且在每一步都调用您之前已经计算过的函数，从而增加了复杂性。上述程序的复杂度是指数级的，但是您可以将其降低到线性时间。

您的代码稍作修改 memoisation :

#include<iostream>
#define NOT_DEFINED -1

using namespace std;

long long memo[1000];

long long fib(int n){
    if(memo[n] != NOT_DEFINED) return memo[n];
    if(n==1 || n==2) return 1;
return memo[n] = fib(n-1)+fib(n-2);
}

int main(){
    for(int i = 0;i < 1000;i++) memo[i] = NOT_DEFINED;
    for(int i=1; i<70; i++)
    cout<<" fib("<<i<<") = "<<fib(i)<<endl;
return 0;
}

Link 到 ideone 上的解决方案：http://ideone.com/jW1VKD

Answer 4

除此之外的其他答案。它越来越慢，因为程序需要 "remember" 计算结果。

如果您必须使用递归，我建议您查看 尾递归。它重用了之前的栈帧。见 Tail recursion in C++

这是一个小例子：

#include <iostream>

int tail_fib(int n, int a, int b) {
  if (n == 0) return a;
  if (n == 1) return b;
  return tail_fib(n - 1, b, a + b);
}

void main() {
  for (int i = 1; i < 45; i++)
    cout << " fib(" << i << ") = " << tail_fib(i, 0, 1) << endl;        
}

Answer 5

递归解决方案的主要问题是它具有 O(2^N) 复杂度。例如。要计算 fib(10)，它必须计算 fib(9)+fib(8)。要计算 fib(9)，它必须计算 f(8) [第二次！] + f(7)。要计算 f(8) [对于第一个总和]，它必须...

最佳解决方案是使用复杂度为 O(N) 的简单循环

unsigned int f(unsigned int n)
{
    unsigned int retVal = 1;

    if (n > 2)
    {
        unsigned int a, b = 1, c = 1;

        for (unsigned int index = 2; index < n; index++)
            a = b, b = c, c = a + b;

        retVal = c;
    }

    return retVal;
}

[巨大的] 差异是由于没有重新计算元素。

您可以通过权衡内存进行运行时间优化 - 分配一个静态向量，每次调用该函数时要么存储以前未计算的值，要么使用那些已经存储的值。

对于程序运行时间内使用的最大 N，这将使内存和运行时间计算复杂度为 O(N)。

Answer 6

我想定量强调一个非常烦人的递归算法属性。

当您调用 fib(1) 或 fib(2) 时，函数 returns 立即执行，因此在这两种情况下执行的调用次数正好是 1。我们写 c(1) = c(2) = 1，其中 c(n) 是执行计算 fib(n).

的调用次数

当您使用 n > 2 调用 fib(n) 时，您间接调用了 fib(n-1) 和 fib(n-2)，总调用次数为 1 + c(n-1) + c(n-2)。

所以c(n)是由递归定义的

c(n) = c(n-1) + c(n-2) + 1,
c(1) = c(2) = 1

这个解叫做列奥纳多数 (https://oeis.org/A001595)。

鉴于递归的形式，您很容易看出这些数字超过了斐波那契数，因此 计算第 N 个斐波那契数比数字本身的值需要更多的递归函数调用。随着斐波那契数呈指数级增长，调用次数也呈指数级增长。

所以它不仅仅是 "more recursive calls"，它是 "massively more recursive calls"。这使得该方法对于大型 n.

非常低效且不切实际

幸运的是，有一种简单的方法可以通过应用递归来迭代计算数字（在其他答案中给出）。

同样感兴趣的是直接公式

Fn = φ^n/√5

四舍五入到最接近的整数，其中 φ 是黄金比例。

Answer 7

这是一个简单的递归版本，它在线性时间 O(N) 内运行。诀窍是 return 两个值而不是一个。

void Fibo(int N, int& F0, int& F1)
{
  if (N == 1) {
    F1= F0= 1;
  }
  else {
    Fibo(N - 1, F0, F1);
    F1= F1 + F0;
    F0= F1 - F0;
  }
}

递归 Finbonacci 优化

Recursive Finbonacci Optimization

c++

recursion

optimization

runtime

fibonacci