【関数型言語】CPS(継続渡し）と末尾再帰最適化
ループと再帰
関数型言語ではループを再帰で表す（ことがおおい）らしい。だが、再帰はスタックオーバーフローする危険がある。それを避けるには、末尾再帰最適化をすればよい。これを使うと、再帰呼び出しにもかかわらず、スタックを消費しない。
scala, haskell, elixir で、合計、階乗、フィボナッチ数について、コードを書いてみた。
study_scala/GettingStarted.scala at master · kzono/study_scala · GitHub
study_elixir/recursiveLoop.ex at master · kzono/study_elixir · GitHub
study_haskell/TailRec.hs at master · kzono/study_haskell · GitHub
acc（アキュムレータ）を引数として追加することによって、再帰的な呼び出しで呼び出された後に実際に行う処理をなくす、というのがポイント。例えば呼び出された先で（関数内の処理として）total + sum(n-1) とするかわりに、関数呼び出すときの引数として足し算を計算してしまう sum(n-1, acc +n) といったかんじ。
どんなループの末尾再帰最適化できるのか？
調べていて気になったのは、「どんなループの末尾再帰最適化できるのか？」ということ。
継続渡しスタイルはクロージャを使った汎用的な方法で、クロージャがあるプログラミング言語であれば、継続渡しスタイルでプログラムを作成することができます。
CPS（Continuation passing style）とは
参考URL
http://practical-scheme.net/docs/tailcall-j.html
http://practical-scheme.net/docs/cont-j.html
CPSを使えば、スタックを消費しない（その代わりヒープを使う）ことができるみたい。全てのループを末尾最適化できるらしい。
継続渡しスタイルの関数では、関数の最後は「継続を表す関数に結果を渡す」ことになりますし*5、 継続渡しスタイルの関数を呼び出す場合もやはり末尾呼び出しになります。 そのため、再帰部分を継続渡しスタイルで書けば自動的に末尾呼び出しになるのです。
つまり、末尾再帰ではない再帰関数をCPS変換したら末尾再帰関数になり、末尾呼び出しの最適化がかかります。
再帰（末尾再帰最適化）の使いどころ
どういう場合に普通のループではなく、（末尾再帰最適化した）再帰呼び出しを使うべきか？また、使うべきでないか？
例えば、「1から10までの合計」といった場合は、通常のループのほうがよさそう。
（再帰関数に慣れてしまえば、ループと同値なのかも）
それに対し、ループの回数が自明でないような、本質的に再帰な課題の場合は、再帰で書いたほうがすっきりかける。漸化式で表せる数列とか、ツリー構造の巡回とか。
