在 C 语言中计算斐波那契递归调用的次数

Question

我面临以下问题：

调用fib(8)（如下），进行了多少次递归调用（忽略第一个）？返回值是多少？

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

所以我做了：

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

int r = 0;

int fib (int n) {
    printf("k: %d fib n: %d", r++, n);
    if (n==0 || n==1) {
        printf("\n");
        return 1;
    } else { 
        printf(" +\n");
        return fib(n-1) + fib(n-2); 
    }
}

int main(int argc, char **argv) {
    int n = atoi(argv[1]);
    int f = fib(n);
    printf("\nreturn: %d\n", f);
    return 1;
}

使用这个我将回答fib(8) = 34递归调用的数量是66。

我对吗？

Answer 1

首先，谎言调用总数 = 67

递归调用 = 66

                   fib(5)   ---root-first call ,not consider recursive call 
                 /           \     
           fib(4)             fib(3)   
         /      \                /     \
     fib(3)      fib(2)       fib(2)    fib(1)
    /     \        /    \       /    \  

- 因为第一次调用不被视为递归调用

现在让我们推导一个计算 fib(n) 被调用次数的公式

令 f(n) 为计算 fib(n) 的调用次数。

如果 n < 2，则 f(n) = 1。

否则，f(n) = 1 + f(n - 1) + f(n - 2)

因此，f 至少为 O(fib(n))。事实上，f(n) 是 2 * fib(n) - 1。

我们通过归纳法来证明这一点：

基本情况（n < 2，即 n = 0 或 n = 1）：

f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1。

归纳步骤（n >= 2）：

f(n + 1) = f(n) + f(n - 1) + 1

f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1

f(n + 1) = 2 * fib(n + 1) - 1

例子

斐波那契(8)=34

所以递归调用= 2*34-1=67

ans=67-1（第一次调用）

斐波那契(4)=5

所以递归调用= 2*5-1=9

ans=9-1（第一次通话）

fib(n) 也可以用 o(logn) 计算

所以整体复杂度降低到 o(logn)

查找 fib(n) 的 O(logn) 和查找递归调用的 O(1)

但你的代码需要指数时间