Java递推斐波那契值

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

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

所以如果这是真的，你们会发现不同的递归函数会导致不同数量的调用来获得序列的第7个值吗？

来源

2015-11-20 flowinwind

查找尾递归：https://gist.github.com/lazywithclass/1402456。这会导致n次呼叫，其中n =第n个斐波纳契值 – jiaweizhang

一个niave方法，另一个使用[**记忆**]（https://en.wikipedia.org/wiki/Memoization）。 –

这取决于你如何编写它。如果你使用memoization，你可以减少调用次数，但是如果你只是'返回n == 0？ 0：n == 1？ 1：fib（n - 1）+ fib（n - 2）;'调用次数确实是'41'。 –

方式一：

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); 
}

其实 '另一个' 的方式是你有多大使表中的任何数量的其他方式，这取决于。当表中有两个元素时，两种方法都是相同的。当它有三个有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); 
}

来源

2015-11-20 02:51:56 EJP

Java递推斐波那契值

回答

相关问题