再帰的にプロセスと反復的プロセス

SICP

問題1.11は、次の定義を再帰的プロセスと反復的プロセスで書けというもの

n < 3 のとき　f(n) = n
n >= 3 のとき f(n) = f( n -1 ) + 2f(n -2) + 3f(n-3)

では、再帰的方法の実装から

saikiF n
        | n < 3 = n
        |otherwise = saikiF ( n-1 ) + 2 * (saikiF ( n -2 )) + 3 * ( saikiF ( n -3 ))

*Main> saikiF 2
2
*Main> saikiF 5
25
*Main> saikiF 10
1892

このやりかただと、saikiF(n-1),saikiF(n-2),saikiF(n-3)を実行していくときに、同じ計算を何度も行うことにより、効率がわるくなってしまいます。(ただ、Haskellは処理系がメモ化を行うから、そこまで遅く ないというのを読んだことがあります。あいまいなので、誰か情報お持ちでしたら教えてください)

というわけで、この関数を反復処理に直します。

hanpuku a b c d
        | d == 0 = c
        |otherwise = hanpuku  ( a + ( 2*b) + (3*c)) a b   (d -1)
hanpukuF n = hanpuku 2 1 0 n

*Main> hanpukuF 2
2
*Main> hanpukuF 5
25
*Main> hanpukuF 10
1892