c - C 中的递归斐波那契

Question

我试图找出为什么这段代码不起作用。

#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。

Answer 1

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

其次，Fibonacci Sequence is defined as要么:

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

或

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

描述它的递归关系是:Fib_n = Fib_n-1 + Fib_n-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。 错误:“fib”未在此范围内声明}