c - C中的递归斐波那契

我试图弄清楚为什么此代码无法正常工作。

#include <stdio.h>

int main()
{
    int num;
    puts("what index of the Fibbonaci series do you want?");

    scanf("%d", &num);

    num = fib(num);

    printf("%d", num);

    return 0;
}

int fib(int num)
{
    if (num == 0)
        return 1;
    else if (num == 1)
        return 1;
    else return (fib(num - 1)+fib(num-2));
}

附言我试图使其尽可能简单，并被告知索引的0和1等于1。

最佳答案

首先，您的函数没有在main()之前声明，这就是为什么您的程序无法运行的原因。

其次，Fibonacci Sequence is defined as要么：

1, 1, 2, 3, 5, 8,...

要么

0, 1, 1, 2, 3, 5, 8,...

其中描述它的递归关系为：Fibn = Fibn-1 + Fibn-2

用C代码转换的代码看起来与您获得的内容类似（上面的第一个定义），或者有点修改（使用第二个同样正确的定义）：

int fib(int num)
{
    if (num == 0) {

        return 0;
    } else if (num == 1) {

        return 1;
    } else {

        return fib(num - 1) + fib(num - 2);
    }
}

注意：

我的函数和您的函数版本都效果不佳，因为它们会进行大量调用，其中大多数会计算重叠值，即它们会计算很多overlapping subproblems。这可以通过使用memoization来解决。

这是使用上述记忆概念的实现示例：

// header needed for the container: map
#include <map>

int mem_fact (int i, std::map<int, int>& m) {

    // if value with key == i does not exist in m: calculate it
    if (m.find(i) == m.end()) {

        // the recursive calls are made only if the value doesn't already exist
        m[i] = mem_fact (i - 1, m) + mem_fact (i - 2, m);
    }

    // if value with key == i exists, return the corresponding value
    return m[i];
}

int fast_factorial (int i) {
    // key (Fibonacci index) - value (Fibbonaci number)
    std::map<int, int> memo;

    // initialize the first two Fibonacci numbers
    memo.insert(std::pair<int,int>(0, 0));
    memo.insert(std::pair<int,int>(1, 1));

    return mem_fact(i, memo);
}

然后在main中，如果您都这样调用：

int slow_fib = fib(10);

int fast_fib = fast_factorial(10);

您将得到相同的结果：slow_fib = fast_fib = 55，但是fib()必须打177次电话，而fast_factorial()仅打19次电话。



1. error: 'fib' was not declared in this scope

关于c - C中的递归斐波那契，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34727143/