在 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

首先 Fib 调用总数 = 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)

但是你的代码需要指数时间