计算每次调用fib(n)的次数n

Question

我想计算每次调用fib(n)的次数.我写的代码如下:

#include <stdio.h>
#define N 10

int count[N + 1]; // count[n] keeps track of the number of times each fib(n) is called

int fib(int n) {
    count[n]++;

    if(n <= 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

int main() {
    for(int i = 0; i <= N; i++) {
        count[i] = 0; // initialize count to 0
    }
    fib(N);

    // print values of count[]
    for(int i = 0; i <= N; i++) {
        printf("count[%d] = %d", i, count[i]);
    }
}

我已经尝试打印数组count []来获得结果,其中结果类似于除[count]之外的斐波那契数字:

count [0] = 34 count [1] = 55 count [2] = 34 count [3] = 21 count [4] = 13 count [5] = 8 count [6] = 5 count [7] = 3 count [ 8] = 2计数[9] = 1计数[10] = 1

有没有办法以数学方式显示这个结果,也许是一个递归公式？另外,为什么不计算[0],或者更确切地说是fib(0),不继续斐波纳契序列？谢谢.

Answer 1

因为count[1]每个人都会被召唤,count[2] + count[3]但是count[0]只会被召唤count[2]...... count[1]因为它是终点所以没有贡献.

至于数学公式:

if n == 0: fib(N - 1)
else: fib(N-(n-1))