c++ - 当我们使用斐波那契数列的递归方法调用 fib(6) 时，fib(3) 被调用多少次？

Question

我遇到了这个问题

How many times does fib(n) gets called when we call fib(k) using the recursive approcah to Fibonacci series? (where k>n)

这里 fib(n) 是使用递归方法给出第 n 个斐波那契数的函数:-

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

我的尝试:
我试图针对 n=3 和 k=6 的特殊情况来做这件事。我发现答案是 fib(6-3+1) = fib(3+1) = 3。下面的流程图展示了它。

它也概括吗？
说这个问题的答案是 fib(k-n+1) 是否正确？
附言请不要只是发布一些代码来回答!请尝试从一般公式的角度思考。

Answer 1

是的，你是对的。 fib(k - n + 1)将给出次数 fib(n)计算时调用 fib(k)递归地，其中 k > n这适用于 n = 0以及。
当我们写代码计算k第 Fibonacci number , 我们给出种子值 fib(0) = 0和 fib(1) = 1这也是使用递归时的终止条件。
来自 Generalizations of Fibonacci numbers :

考虑这个例子，假设 不是 给定种子值 f(0) = 0和 f(1) = 1 :

  // read f(x) as fibonacci(x)
                                   f(4)
                                    |
                  -------------------------------------
                  |                                   |
                 f(3)                                f(2)
                  |                                   |
          -----------------                  --------------------
          |               |                  |                  |
         f(2)            f(1)               f(1)               f(0)
          |               |                  |                  |
      ---------      ----------         ----------         -----------
      |       |      |        |         |        |         |         |
     f(1)    f(0)   f(0)     f(-1)     f(0)     f(-1)     f(-1)     f(-2)
      |       |      |        |         |        |         |         |
    -----   -----  -----    -----     -----    -----     -----     -----
    |   |   |   |  |   |    |   |     |   |    |   |     |   |     |   |
  f(0) f(-1)|   |f(-1)f(-2) |   |  f(-1) f(-2) |   |  f(-2) f(-3)  |   |
    |       |   |           |   |              |   |               |   |
    |    f(-1) f(-2)     f(-2) f(-3)        f(-2) f(-3)         f(-3) f(-4)
  -----
  |   |
f(-1) f(-2)
 .....
 ..... and so on

现在让我们计算 f(n) 的数量调用 f(4)使用 f(4 - n + 1) , 其中 n < 4 :

n = 3  ==>  f(4 - 3 + 1)   ==> f(2) ==> 1  --
n = 2  ==>  f(4 - 2 + 1)   ==> f(3) ==> 2   |
n = 1  ==>  f(4 - 1 + 1)   ==> f(4) ==> 3   |-  Number of time f(n) called when calculating f(4)
n = 0  ==>  f(4 - 0 + 1)   ==> f(5) ==> 5   |   cross check it with recursive call trace shown above
n = -1 ==>  f(4 -(-1) + 1) ==> f(6) ==> 8  --
.....
..... and so on

编辑:
斐波那契的双向序列是(基于上面链接中的公式):

----------------------------------------------------------------------------------
... f(−4) | f(−3) | f(−2) | f(−1) | f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) ....
----------------------------------------------------------------------------------
... −3    | 2     | −1    | 1     | 0    | 1    | 1    | 2    | 3    | 5    | 8 ....
----------------------------------------------------------------------------------

从这个序列中，fib(-3) = 2和 fib(-4) = -3 .让我们使用这些值作为递归的终止条件而不是 fib(0) = 0和 fib(1) = 1 :

#include <stdio.h>

int fib(int n) {
        if (n == -3) {
                return 2;
        }

        if (n == -4) {
                return -3;
        }

        printf ("recursive call - fib(%d) + fib(%d)\n", n - 1, n - 2);
        return fib(n - 1) + fib(n - 2);
}

// This is a test program to prove OP number of calls to f(n)
// when calculating f(k), where n < k

int main(void) {
        int n;
        printf ("Enter a number (>= -4):\n");
        scanf ("%d", &n);

        // Input less than -4 not allowed as -4 is
        // the least seed value provided which is also  
        // a terminating condition of recusive function
        // calculating kth fibonacci number

        if (n < -4) {
                return 0;
        }

        printf("Fibonacci Number at location %d in series : %d\n", n, fib(n));    return 0;
}

输出:

# ./a.out 
Enter a number (>= -4):
4
recursive call - fib(3) + fib(2)
recursive call - fib(2) + fib(1)
recursive call - fib(1) + fib(0)
recursive call - fib(0) + fib(-1)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(0) + fib(-1)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(1) + fib(0)
recursive call - fib(0) + fib(-1)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
Fibonacci Number at location 4 in series : 3

在输出中，次数f(0)计算时调用 f(4)与 f(k - n + 1) 计算的相同哪里k = 4和 n = 0 (满足条件 k > n)和 0不是最小的值。