線形時間の反復計算

ちょっと間が空いてしまったけれど、ガウディ本の3.4節について。


再帰計算で問題になる点として、

1.入力の大きさの2乗に比例した計算時間が必要になる
2.入力の大きさに比例してスタックが大きくなる

という点があげられる。

この問題を3.4節では再帰計算を反復計算に変換することで解決している。

簡単には、常に状態を先送りし、戻ってきてから計算しないことである。
具体的には

declare
fun {Factorial X}
  if X==0 then 1
  else X*{Factorial X-1}
  end
end

とした場合、戻ってきてから計算している。
つまり、X=5なら、(5*(4*(3*(2*1))))
しかし、次の場合は

declare
fun {Factorial I X}
  if X==0 then I
  else {Factorial I*X X-1}
  end
end

状態を先送りにしている。(もちろんI=1で最初に呼び出す必要があるが・・・)
つまり、X=5なら、((((1*5)*4)*3)*2)

このようにすることで、スタックの増大を抑えられる。

広告を非表示にする