在Haskell

評估遞歸函數，我給這個函數，並要求手動評估g 5。我發現答案是25，但這是不正確的。正確答案是63.有人能幫我理解爲什麼嗎？感謝在Haskell

g :: Int -> Int 
g n 
    | n==0  = 1 
    | otherwise = 2 * g (n-1) + 1

我的回答：（2 * 4 + 1）+（2 * 3 + 1）+（2 * 2 + 1）+（2 * 1 + 1）+ 1 = 25

來源

2016-12-31 Pete

有多少次你嘗試對其進行評估？可能你只是搞砸了一些計算。也許寫下爲什麼你認爲它應該是42，所以我們可以指出你的錯誤。 – jpath

你只需要一步的想出來步：

(g 5) = 2 * (g 4) + 1 
(g 4) = 2 * (g 3) + 1 
(g 3) = 2 * (g 2) + 1 
(g 2) = 2 * (g 1) + 1 
(g 1) = 2 * (g 0) + 1 
(g 0) = 1

然後，插頭從底向上的價值觀：

2 * 1 + 1 = 3 
2 * 3 + 1 = 7 
2 * 7 + 1 = 15 
2 * 15 + 1 = 31 
2 * 31 + 1 = 63

你的問題是，你正在使用的原始值0，而不是在遞歸的終點返回什麼(g n)。

來源

2016-12-31 12:44:02 Carcigenicate

在你的計算中，你會混淆術語的嵌套。它們應該嵌套而不是分開總結。

評估此類函數的方法是將函數應用程序替換爲函數體，其參數由給定參數替換。我會做的前幾個步驟，然後你可以接管：

g 5 
if 5 == 0 then 1 else 2 * g (5-1) + 1 
2 * g (5-1) + 1 
2 * (if (5 - 1) == 0 then 1 else 2 * g ((5-1) - 1) + 1) + 1 
2 * (if 4 == 0 then 1 else 2 * g (4-1) + 1) + 1 
2 * (2 * g (4-1) + 1) + 1 
... 
63

@ Carcigenicate的回答當然是容易計算，但這種技術更普遍，更內嵌代碼是如何實際工作。

來源

2016-12-31 12:49:58 jpath

雖然這不是你的問題，它很容易被歸納證明

g n = 2^(n+1)-1

所以

g 5 = 2^6 - 1 --> 63

來源

2016-12-31 23:20:09 RussAbbott

你的括號是錯誤的。沒有做任何的減少（比擴大g等），我們得到

g 5 
= 2 * g 4 + 1 
= 2 * (2 * g 3 + 1) + 1 
= 2 * (2 * (2 * g 2 + 1) + 1) + 1 
= 2 * (2 * (2 * (2 * g 1 + 1) + 1) + 1) + 1 
= 2 * (2 * (2 * (2 * (2 * g 0 + 1) + 1) + 1) + 1) + 1 
= 2 * (2 * (2 * (2 * (2 * 1 + 1) + 1) + 1) + 1) + 1

來源

2017-01-02 18:36:16

回答

相關問題