我不明白給定的斐波那契對haskell函數（元組）

遞歸是我一直在努力理解的東西。我希望我能在這裏得到一些關於這個功能如何工作的幫助。它的工作原理，但我想知道如何：我不明白給定的斐波那契對haskell函數（元組）

fibStep :: (Int,Int) -> (Int,Int) 
fibStep (u, v) = (v, u+v) 

fibPair :: Int -> (Int,Int) 
fibPair n 
    | n==0  = (0,1) 
    | otherwise = fibStep (fibPair (n-1))

來源

2011-05-17 maclunian

你能解釋一下你到底想到了什麼嗎？ – 2011-05-17 00:23:31

@Dhaivat Pandya我知道'fibStep'函數的作用。我只是不知道'fibPair'函數以及它與fibStep的關係。 – maclunian 2011-05-17 00:26:56

我最近寫了一個類似問題的答案，它可能也會幫助你：http://stackoverflow.com/questions/5999356/trying-to-get-my-head-around-recursion-in-haskell/5999433#5999433 – sarnold 2011-05-17 00:40:54

遞歸很像一個循環。對於循環，你有一個停止條件，遞歸也是如此，除了它被稱爲基本情況。在這個斐波納契的例子中，基本情況是n==0，它返回元組(0,1) - 當然這代表第一個斐波那契數。

確定基本情況後，現在需要確定遞歸步驟 - 在本例中爲fibStep (fibPair (n-1))。這相當於循環的代碼塊，或者在每次迭代中重複執行的步驟，直到達到基本情況。當然，確保您總是收斂到基本情況至關重要，否則遞歸將永遠不會結束 - 在此示例中，遞歸步驟確實會收斂到基本情況，因爲對於每個連續步驟，值爲n減1，這意味着我們最終必須達到n==0（假設n最初爲正）的情況。

讓我們看看fibPair 3的評估。使用示例中提供的定義，每個連續行都是前一個行的擴展。

fibPair 3 **note: n is not 0 so we use the recursive step 
fibStep (fibPair (3-1)) 
fibStep (fibPair 2) **note: n is not 0 use recursive step again 
fibStep (fibStep (fibPair (2-1))) 
fibStep (fibStep (fibPair 1)) **note: n is not 0 use recursive step again 
fibStep (fibStep (fibStep (fibPair (1-1)))) 
fibStep (fibStep (fibStep (fibPair 0))) **note: n equals 0 so base case is used 
             ** recursion has now ended 
fibStep (fibStep (fibStep (0,1))) **note: now fibStep begins evaluation 
fibStep (fibStep (1, 1)) 
fibStep (1, 2) 
(2, 3)

重要的是，您應該對發生的事情的英文解釋感到滿意。 fibStep取一個(fib number x, fib number x+1)的元組並依次返回下一個元組，即(fib number x+1, fib number x+2)。 fibPair充當fibStep的循環，導致fibStep在同一元組上被調用n次，這意味着元組(fib number x, fib number x+1)將導致爲(fib number x+n, fib number x+n+1)。

希望這有助於澄清一些事情。遞歸確實是寫一個循環的另一種方式;它具有所有相同的元素，但寫法有點不同。對於使用遞歸結果的一些問題更簡單的邏輯或代碼或兩者兼而有之。一旦你對遞歸更加適應，它將成爲你未來編程的一個非常有用的工具。

來源

2011-05-17 00:47:08 erisco

＃n！= 0是什麼意思？ – maclunian 2011-05-17 00:51:01

n不等於0.這是許多語言中流行的符號。在Haskell中，會使用'not n == 0'。散列只是開始評論的符號;它不是表達的一部分。 – erisco 2011-05-17 00:57:57

或n/= 0. Haskell符號來源於劃出的等號的數學符號。 – fuz 2011-05-17 05:33:42

一般情況下，當過你在做遞歸，儘量向後工作，並與小值，例如，如果我們通過fibPair其中n = 0，則立即返回(0,1) 。

然後，如果n = 1，我們得到，

fibPair 1 = fibStep (fibPair 0) = fibStep (0, 1) = (1,1)

，以n = 2，我們得到，

fibPair 2 = fibStep (fibPair 1) = fibStep (1,1) = (1,2)

所以，我們可以看到，它給你的第n對斐波納契序列從(0, 1)中提起。

如果你還沒有真正瞭解它，嘗試全面拓展了fibPair 2（即擴大了fibStep (fibPair 1)）

來源

2011-05-17 00:37:43

不能'fibPair 2'必須返回到fibPair 0才能給出答案？如果沒有，這根本就沒有意義！ – maclunian 2011-05-17 00:45:43

Pandya已經擴展了'fibPair 1'，所以爲了簡潔起見，他們沒有再爲「fibPair 2」擴展它。 – erisco 2011-05-17 00:57:15

@maclunian是的。由於'fibPair 1'的擴展已被解釋，Dhaivat忽略了這一步驟的簡潔性。完整的擴展將如下所示：'fibPair 2' =>'fibStep（fibPair 1）'=>'fibStep（fibStep（fibPair 0））=>'fibStep（fibStep（0,1））'=>'fibStep （1,1）'=>'（1,2）'。 – Ergwun 2011-05-17 00:59:09

我不明白給定的斐波那契對haskell函數（元組）

回答

相關問題