ハスケルで再帰関数を評価する

Question

私はこの関数を与えられ、g 5を手動で評価するように求められました。答えが25であることがわかりましたが、これは間違っています。正解は63です。なぜ誰かが私の理解を助けるでしょうか？おかげ

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

私の答え：（2 * 4 + 1）+（+ 1 2 * 3）+（2 * 2 + 1）+（2 * 1 + 1）+ 1 = 25

Answer 1

あなただけのステップバイステップでそれを考える必要があります：

(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)が返されます。

Answer 2

あなたの計算では、用語のネストを混乱させました。それらはネストされ、別々に集計されるべきではありません。

このような関数を評価する方法は、関数のアプリケーションを、その引数を指定された引数で置き換えて関数の本体に置き換えることです。私は、最初のいくつかの手順を行いますし、あなたが引き継ぐことができます。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 

はもちろん、計算が容易であるが、この技術は、コードが実際にどのように動作するかをより普遍的かつよりインラインです。

Answer 3

これはあなたの質問はありませんが、それは

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

だから

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

Answer 4

あなたのカッコが間違っていることを誘導することによって示すことは非常に簡単です。縮小を行わない（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