ちょっと間が空いてしまったけれど、ガウディ本の3.4節について。
再帰計算で問題になる点として、
1．入力の大きさの２乗に比例した計算時間が必要になる
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)
このようにすることで、スタックの増大を抑えられる。
