Java递归斐波那契值

Question

问题:递归计算第 7 个斐波那契值需要多少次调用？

所以这是给我的一个问题，给我的答案是41。然后我去找一位教授，因为我不明白，但我得到了另一个答案。我记得是25？ (不要引用我的话)然后我去找另一位教授......他告诉我给你这个问题的人应该给你示例代码，因为可以有多种方法来编写这个递归函数，这会导致不同数量的调用。

如果这是真的，你们能找到不同的递归函数，这些函数会导致获得序列的第 7 个值所需的调用量不同吗？

Answer 1

一种方法:

static long fibonacciR(int i)
{
    if (i <= 1)
        return i;
    return fibonacciR(i - 1) + fibonacciR(i - 2);
}

另一种方式:

static final int    f[] = {0,1,1,2,3,5,8,13,21,34,55,89,144};
static long fibonacciR2(int i)
{
    if (i < f.length)
        return f[i];
    return fibonacciR2(i-1)+fibonacciR2(i-2);
}

事实上，“另一种”方式是任意数量的其他方式，具体取决于您制作的表格有多大。当表有两个元素时，两种方法是相同的。当它有 3 个时，就有 25 个调用。 4、15 时。依此类推。

还有另一种方式，专门接到 25 个电话:

static long fibonacciR3(int i)
{
    if (i == 0)
        return 0;
    if (i <= 2)
        return 1;
    return fibonacciR(i - 1) + fibonacciR(i - 2);
}