フィボナッチ数計算(続　再帰的・反復的)

PG Haskell SICP

再帰的プロセスは、計算の木構造をめいっぱい展開することになる。
だから再帰的プロセスより反復的プロセスのほうが低コスト。
以下、反復的プロセスが、再帰的プロセスよりも低コストになる典型例

  • 再帰版フィボナッチ数計算
-- フィボナッチ数(高コスト)
myfib_r n = case n of
              0 -> 0
              1 -> 1
              _ -> myfib_r (n-2) + myfib_r (n-1)

(myfib_r 5) を計算するときに(myfib_r 4)と(myfib_r 3)を計算している。(myfib_r 4)では、(myfib_r 3)の値を計算している。(myfib_r 5)を計算するときに求める(myfib_r 3)は、(myfib_r 4)を計算するときに求める(myfib_r 3)を利用せず、別に1から計算しなおしている。だから、引数nが大きくなればなるほど高コスト。しかもフィボナッチ数は指数関数的に増える。

  • 反復版フィボナッチ数計算
-- フィボナッチ数(低コスト)
myfib_i n = let
            {
              myfib_iter a b cnt
                = case cnt of
                    0 -> b
                    _ -> myfib_iter (a+b) a (cnt-1)
            } in myfib_iter 1 0 n