在递归算法中获得更快的代码

Question

我正在学习 C 中的递归。我的问题是：打印 80 个第一个斐波那契数（使用递归）

这是本书的代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long f[100];

long long fib(int n)
{
    if (n<2) return 1;
    if (f[n]>0) return f[n];
    f[n] = fib(n-1)+fib(n-2);       
    return f[n];
}
int main()
{
    int i;
    for (i = 0; i<= 80; i++) printf ("%lld \n", fib(i));
    system ("pause");
    return 0;
}

使用这段代码，我的程序运行得非常快，我立即得到了 80 个斐波那契数列。

但是，当我删除第 10 行时：

if (f[n] > 0) return f[n];

程序变得很慢，打印所有80个数字大约需要20秒。谁能解释为什么？谢谢。

Answer 1

那是因为缓存的结果不再以这种方式使用。你看，当你使用递归函数时，例如 f(20) 被多次调用，试着在纸上画出调用树，你就会看到。该行所做的基本上是避免重新计算这些值（记忆，如果你想这样说的话）。

Answer 2

该算法正在缓存数组 f 中先前计算的值。这个数组用 0 初始化（因为它是静态的）。考验你提到删除检查是否有缓存值，并且 returns 它。经过消除测试，你永远不会使用缓存的值，而是重新计算它每次。这很昂贵，因为您最终要计算相同的值很多很多次。

编辑：

我可能会补充一点，如果这是书中的代码，你应该得到一个不同的书，因为画风很差。在 C 中，我会这样写：

long long
fib( int n )
{
    static long long cache[100];    //  limit scope, and give it a good name
    assert( n >= 0 && n < sizeof(cache) / sizeof(cache[0]) );
                                    //  make sure input is legal.
    if ( cache[n] == 0 ) {
        cache[n] = n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 );
    }
    return cache[n];
}

您会注意到，这样代码实际上要简单得多。

在 C++ 中，当然，我会使用 std::vector 作为缓存，所以我没有一些隐藏的、硬编码的限制。（就此而言，在 C 中，我可能会实现类似的东西，以避免硬编码限制。但是我不会期望在教学示例中。）

Answer 3

首先，如果您使用朴素的递归公式（即，如果您在代码中注释第 10 行）

F(n) = F(n-1) + F(n-2)

如您所见，它多次计算许多值（因此效率低下），或者换句话说，随着每个节点解析为 2 个分支（O(2^n)）

，时间复杂度呈指数级增长

因此，如果他保存我们的工作并使用它来解决再次发生的相同问题：我们可以实现线性时间复杂度 ( O(n) )

在您的代码中，数组 f 是 cache

但是，如果您有兴趣知道（尽管没有被问及），您可以通过矩阵指数以对数时间复杂度计算 Fib(n) 或通常比这更快的任何线性递归关系。 ( O(logN) )

Answer 4

这种解题思路叫做动态规划，这种特殊的方法叫做记忆：

http://en.wikipedia.org/wiki/Dynamic_programming

这个想法是存储以前计算的值并使用它们而不是再次计算它们。在您的情况下，它们存储在：f[100] 并且一旦计算出斐波那契数，就永远不会重新计算。当您删除分配时，您会禁用此存储并且每次都会重新计算值。

在递归算法中获得更快的代码

Get a faster code in recursion algorithm

c

c++

recursion

fibonacci