如何做斐波納契遞歸作品在C＃

Question

我想很難理解下面的菲波納契碼：

private static int mtdFibonacci(int number) 
    { 
     if (number == 0) return 0; 
     if (number == 1) return 1; 

     return fncRecursive(number - 1) + fncRecursive(number - 2); 
    } 

基本上，我有一個很難創建它作爲是如何做到的7輸入功能，等於到13.雖然答案是正確的，因爲斐波那契序列的第7個元素是13：

1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th 
1 1 2 3 5 8 13 21 34 55 

現在我試圖複製代碼我自己的論文討論瞭如何斐波納契遞歸工作以及如何C＃中解決這個問題：

if n is 7: 
return F(7) = F(7-1) + F(7-2) 
return F(7) = F(6) + F(5) 
return F(7) = [F(5) + F(4)] + [F(4) + F(3)] 
return F(7) = {[F(4) + F(3)] + [F(3) + F(2)]} + {[F(3) + F(2)] + [F(2) + F(1)]} 
return 15? 

我試圖在線檢查，但沒有解釋如何正確的遞歸函數爲斐波那契序列工作。代碼是正確的，輸出是正確的，但我不能在上面的紙張序列上覆制它。就像7的輸入對我來說是15。

Answer 1

你只需要小心地擴展你的序列，就是這樣，這裏沒有魔法。

F(7) = F(6) + F(5) 
    = F(5) + F(4) + F(4) + F(3) 
    = F(4) + F(3) + F(3) + F(2) + F(3) + F(2) + F(2) + F(1) 
    = F(3) + F(2) + F(2) + F(1) + F(2) + F(1) + F(2) + F(2) + F(1) + F(2) + F(2) + F(1) 
    = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 
    = 13 

Answer 2

{[F(4) + F(3)] + [F(3) + F(2)]} + {[F(3) + F(2)] + [F(2) + F(1)]} 
= 3 + 2 + 2 + 1 +  2 + 1 + 1 + 1 = 13 

Answer 3

的我在讀你的問題是什麼，上面的算法背後的邏輯。我堅信一件事是「一種尺碼不適合所有人」，這是一個很好的例子。

計算第n個斐波納契數的一個快速解決方案是遞歸地添加數字直到第n個循環結束。相反，上述算法試圖以相反的順序推導第n個斐波納契數。

這裏的目標是找到其定義必須是前兩個數字這反過來將是前兩個數字的總和的總和n個斐波納契數。

按照這個定義，你可以從圖中看到我創建的x必須是y = x - 1和z = x - 2等的總和。

Answer 4

下面是我喜歡向初學者解釋遞歸的一種方法。

讓我們想象一下一個稍微簡單的「僞代碼」語言程序的版本：

f(n) => if n < 3 then 1 else f(n-1) + f(n-2) 

這不是合法的C＃，但在閱讀它，並確保你瞭解這裏的部分。

現在我們打一個小遊戲，只是文字。遊戲規則是：

• 如果我們看到f(some number)那麼我們用(the if expression with all the n's changed to some number)替換它。

我們在一分鐘內需要更多的規則，但讓我們從這一條開始。假設我們有：

f(5) 

我們遵循規則。我們與

(if 5 < 3 then 1 else f(5-1) + f(5-2)) 

下一頁規則替代它：

• number < number被替換或者true或false
• number - number被替換它們的區別
• number + number替換它們的總和。
• (number)被替換number只要沒有f以前( .F

OK，應用這些規則：

(if false then 1 else f(4) + f(3)) 

決賽規則：

• if false then X else Y被替換Y. if true then X else Y被替換爲X.

應用它：

(f(4) + f(3)) 

現在再次提出申請的第一個規則：

((if 4 < 3 then 1 else f(4-1) + f(4-2)) + (if 3 < 3 then 1 else f(3-1) + f(3-2)) 

保持應用規則：

((if false then 1 else f(3) + f(2)) + (if false then 1 else f(2) + f(1)) 
(f(3) + f(2)) + (f(2) + f(1)) 

讓我們跳過了幾步這裏。您將看到f(3)是要與(f(2) + f(1))被替換，即f(2)和f(1)要與(1)更換，對不對？

(((f(2) + f(1)) + (1)) + ((1) + (1)) 
(((f(2) + f(1)) + 1) + (1 + 1) 
(((f(2) + f(1)) + 1) + (2) 
(((f(2) + f(1)) + 1) + 2 

再次跳過了幾步。如果他們不清楚，那就親自去做吧

((((1) + (1)) + 1) + 2 
(((1 + 1) + 1) + 2 
(((2) + 1) + 2 
((2 + 1)) + 2 
((3)) + 2 
(3) + 2 
3 + 2 
5 

然後我們就完成了。通過一些簡單的字符串替換規則，我們推斷f（5）等於5.

您可以將函數激活看作是簡單函數中的一般函數，就像這樣：「如果函數體具有所有的形式參數都被他們的參數值所取代？「如果你這樣想，那麼遞歸就變得更直接了。

當然，這是不是這是如何真正運行時實現的，這忽略了很多控制流，變量突變，等等方面。但是，以此來了解遞歸在你的職業生涯的早期，我認爲這是一個相當不錯的。