まぁしょうもない問題もパズルみたいで、ある意味面白いのですが。今日は、Erlangプログラミングで最も重要な概念とも言えそうな再帰について勉強していきます。
target="_blank">CC BY-NC-SA 3.0ではなく
target="_blank">CC BY-SA 2.5です。
Tail recursionとNon-tail recursionの違いは、ざっくり言うと、
1) Non-Tail recursion:
次の関数呼び出しをした後も、元のスタックフレームが情報を保持していなければならないもの。
2) Tail recursion:
次の関数呼び出しを行ったら、元のスタックフレームが必要なくなるもの。
取りあえず今のところ、例えばJavaではTail recursionだからといって元のスタックフレームを捨てる最適化(tail call
optimization)を行えず、折角必要なくなっているのにスタックフレームを捨てないので、そういう言語ではそれほど重要な違いではないのですが、Tail call
optimizationを行うErlangでは、Tail recursionはconstant memory space (=メモリの使用量のオーダがO(1))で実行できるのに対し、Non-tail
recursionはできないという根本的な違いが出てきます。
Java出身の人間にわかりやすい言い方をすると、Non-tail
recursionではスタックオーバーフローによっていずれプロセスがお亡くなりになってしまいますが、Erlangでは、Tail
recursionだと、無限ループが可能になります。Javaであれば、Tail
recursionであろうがやはりスタックオーバーフローに陥りますが、これは、上で述べたとおり、JVMがErlangと違ってtail call
optimizationを行わないからです（詳しくは
target="_blank">こちら）。
Erlangでは、たくさんのプロセスがあたかもモノというか、会社の部署のようにコミュニケーションしながら働きます。一つ一つのプロセス（アクター）は、それぞれ独立していて、お互いいわばメールでしか干渉せず、基本的には部署ごとで働いているイメージです。このようなプログラミングモデルをアクターモデルというのですが、このアクターを作るとき、実はこのtail recursionによる無限ループを使うのです。なので、これをマスターしないと、Erlangの一番のミソが使えないということになってしまいます。
さて、例をあげて、tail recursionとNon-tail recursionの違いをより直感的に見ていきます（
target="_blank">USCのLorin氏の解説をもとにしています）。
あるNを与えられたら、1からNまでを足し合わせる関数を考えます。
sum(5) = 1 + 2 + 3 + 4 + 5 = 15
Non-tail recursionでは、このように書けます。
recsum(5)をコールした場合、計算は次のように実施されます：
recsum(5)
5+recsum(4)
5+(4+recsum(3))
5+(4+(3+recsum(2)))
5+(4+(3+(2+recsum(1))))
5+(4+(3+(2+1)))
15
一番上のスタックフレームは、まだ 5 + recsum(x-1) の「5 + ?」の計算をしないといけないので、スタックフレームにあるものを一旦保存しなくてはいけませんね。
それに対して、tail recursionでは次のように書けます：
※("def tailrecsum(x,running_total=0)" はpythonの書き方で、変数名=数値として関数を定義しておくと、tailrecsum(x)と書くと自動的にtailrecsum(x,0)を呼び出してくれます（デフォルト引数と言います）。
先程は計算の手順なんかを保存して置かなければいけませんでしたが、今回は"小計"を変数として渡していくので、その必要がなくなります。
計算はこのように進んでいきます。
tailrecsum(5,0)
tailrecsum(4,5)
tailrecsum(3,9)
tailrecsum(2,12)
tailrecsum(1,14)
tailrecsum(0,15)
15
計算の手順がたまっていくのではなく、値がアップデートされながらバトンタッチされていくというこころが、tail recursionのミソです。
では、Erlangで書いてみましょう。
なんとなくNon-tail recursionの方がスマートですね。こう考える人は多いみたいで、「必要に迫られなければ、tail recursionは基本使わない」という人もいるようです。
昔はTail recursionの方がずっと早かったり、メモリ消費量がずっと小さかったりしていたらしいのですが、様々な最適化のおかげで、今は一概にどちらがよいとも言えなくなったそうです。
なので、「お好きな方で」やって、必要ならパフォーマンステストして比べなさいというのが最近のErlangのガイドラインのようです。
参考：http://stackoverflow.com/questions/33923/what-is-tail-recursion
