CPSを学ぶためにまるごとJavaScript & Ajax ! Vol.1を引っ張り出してきたけど、その前に末尾再帰を学ぶ。
末尾再帰とは
末尾再帰（まつびさいき）とは、プログラミング手法のひとつで、再帰のある関数またはプロシージャのおこなうべき最後のステップが、関数またはプロシージャの再帰的な呼び出しになるようにすることである。
末尾再帰 - Wikipedia
関数型言語と単一代入
関数型言語では変数への代入は一度しか行わず、再代入しない(できない？？)。
だからたとえば1から10までの合計を算出するとき、ループを使うと関数型的ではない。
// ループを使って1から10までの合計を算出する var sum = 0 for(i <- 1 to 10) { // sumに再代入している(単一代入ではない) sum += i } println("ループ：" + sum)
上記の雑誌p197を参照。ASのコードをScalaにした。
ループではなく再帰を使う
再代入せず、単一代入でこの処理を実現しようとすると、再帰を使う必要がある。
// 末尾再帰で1から10までの合計を算出する def sumIter(i: Int, sum: Int): Int = { if(i > 10) { sum } else { sumIter(i + 1, sum + i) } } println("末尾再帰：" + sumIter(1, 0))
同じく上記の雑誌p197を参照。
この再帰だと
- sumIter(1, 0)
- sumIter(2, 1)
- sumIter(3, 3)
- sumIter(4, 6)
- sumIter(5, 10)
- sumIter(6, 15)
- sumIter(7, 21)
- sumIter(8, 28)
- sumIter(9, 36)
- sumIter(10, 45)
で10 + 45を計算して55となる。
再帰と末尾再帰
再帰呼び出しをするということは、再帰的に呼び出した関数から戻り値が戻ってきたあとの処理を情報として保存しておく必要がある。
この情報を「継続」というらしい。何やらCPS(継続渡しスタイル)につながりそうだ。
一般に，再帰がメモリーを消費するのは，関数を呼び出すたびに，「関数が返ってきた後にする処理」の情報を保存しなければならないからだ（詳しい人のために：この情報が「継続」(continuation)である。命令型言語にせよ関数型言語にせよ，ほとんどの言語処理系では，関数呼び出しの継続はスタックに保存される。
第2回 「単一代入」と「末尾再帰」：ITpro
再帰呼び出しのあとに「後に続く処理」がなければ、情報を保存する必要がなくなるわけだ。
こういう呼び出しが「末尾呼び出し」であり、再帰呼び出しすべてが末尾呼び出しであれば「末尾再帰関数」というらしい。
「関数が返ってきた後にする処理」がなければ，関数呼び出しは単なるgotoとしてコンパイルできる。そのような「後にする処理」がない関数呼び出しのことを「末尾呼び出し」という。特に，すべての再帰呼び出しが末尾呼び出しであるような再帰関数のことを「末尾再帰関数」という。
第2回 「単一代入」と「末尾再帰」：ITpro
