maeshimaの日記

メモ書きです

末尾再帰最適化

名前だけ知ってて、実際どういうものか知らなかったけど、下記エントリを読んで大体理解できたと思う。

再帰は再帰なんかじゃない!末尾再帰こそが真の再帰なんだ! - hp12c
Rubyの末尾再帰最適化を理解する - hp12c

末尾再帰とは

  • 再帰的に実行するメソッドの結果を待たなくてもいい
  • メソッドローカルな変数を持たない

再帰のメソッド。

メソッドの結果を待ったり、メソッドローカルな変数を持つ必要があると、メモリが解放されず、再帰が深い場合にエラーになる。

末尾再帰最適化とは

読んで字のごとく、末尾再帰になるように最適化すること。上記に上げたエントリ中では、

  • tcoメソッドの中に引数を一時的に保存する変数を作る
  • クロージャで、メソッド中で使われる変数を共通化(tcoメソッド中のスコープに外だし)

のようにして、メソッドローカル変数を使わないようにしていた。