末尾再帰最適化

概要

Tail Call Optimization(TCO

再起呼び出しをwhileループに変換すること

関数を呼び出すとコールスタックに戻ってくるアドレスを積むことになる→再帰呼び出しが深くなるとStackOverflowしてしまう→等価なwhileループに変換することで回避

hiroki.icon要はコールスタックのマネジメントだね。高級プログラミング言語やっているとコールスタックなんて考えないから難しく感じる

末尾再帰→gotoといえる

継続的説明

呼び出して継続の後処理がない場合は最後の処理で一番上の呼び出し元までジャンプして戻っても同じことなので最適化できるよねって話

https://gyazo.com/d22b95192ced84b6a941cf8d65260b7a

条件と例

関数のreturnが定数である

関数のreturnが自分自身の再帰呼び出しのみである

ok:case ... => me(...)

ng:case ... => me(...) + 1

ngでは再帰的にmeを読んだ後に+1するという後続の処理があるため、このポイントを記憶して置かなければいけない→末尾最適化できない

相互再帰では最適化されない

code:scala

def even(n: Int): Boolean =

if (n <= 0)

true

else

odd(n - 1)

def odd(n: Int): Boolean =

if (n <= 0)

false

else

even(n - 1)

scala> even(100000)

java.lang.StackOverflowError