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遞推斐波那契值

回答

相關問題