再帰処理の問題点
プログラミング言語で関数呼び出しをするときは、コンピュータ内部で以下のような事をやっています。
１．関数を呼び出しする前に、戻り場所を覚える。
２．関数を呼び出す（＝実行する）。
３．関数の呼び出しが終了したら、覚えておいた戻り場所を取り出して、プログラムの実行をその場所から再開する。
再帰処理においては、手続き内から、自分の手続きを何度も何度も呼び出すため、とてもたくさんの戻り場所を覚えなくてはいけません。呼び出す手続きがたとえ同じであっても、呼び出す箇所が変化しているので都度戻る場所を覚えなければいけません。すると、そのうち戻り場所を覚えられなくなってしまい、プログラムが異常終了してしまいます。
末尾再帰
この問題を解決するには「末尾再帰」という書き方で手続きを書く必要があります。
(Scheme 言語に限ります。他のプログラミング言語の場合は末尾再帰で書いたとしても解決できるとは限りません。)
sum 手続きを例に説明します。
(define (sum items)
(if (null? items)
0
(+ (car items))
(sum (cdr items))))
これはリストの入れ子を考慮しない、単純な sum 手続きです。これを末尾再帰で書いてみます。
(define (sum items)
(define (iter lst sum)
(if (null? lst)
sum
(iter (cdr lst) (+ (car lst) sum))))
(iter items 0))
sum 手続きに内部手続き iter を用意して、iter 手続きの引数に sum を持つようにします。
sum 手続きは、内部手続き iter を、lst に items を、sum に 0 を指定して評価します。
lst が空リストの場合は 0 ではなく sum を返します。
lst が空リストでない場合は、
１．iter の lst には (cdr lst) を指定して、次の処理の準備をします。
２．iter の sum には、(car lst) つまり先頭の要素を sum と足し算した結果を指定します。
このようにすることで sum には各要素を合計した値で更新されていき、リストが空になったとき最終的な合計が格納されます。特に２．の部分は他プログラミング言語で書くところの
sum = sum + var
と同じです。Scheme ではいわゆる「代入」を使わずに、「引数に何かを足し算したものを新しい引数にして再帰呼び出しする」として値を加えるという操作をします。
ここで、内部手続き iter は、最後の行で再帰呼び出しをする書き方になっています。この書き方を「末尾再帰」と言い、Scheme においては末尾再帰を使って手続きを書けば、再帰呼び出しの際に戻り場所を覚えなくても済むように設計されています。
実行
gosh> (sum '(1 2 3 4 5))
15
実行しただけでは、変化はわかりづらいと思います。trace 手続きを使うと違いがわかるのですが、ここでは割愛します。
まとめ
今回は末尾再帰を説明しました。Scheme においては、末尾再帰で手続きを書けば、どれだけ再帰呼び出しをしてもプログラムが異常終了することはありません。
蛇足
個人的には末尾再帰の書き方は好きではありません。私の価値観では末尾再帰でない普通の書き方のほうがはるかにエレガントです。さらに、コンピュータの内部の都合でプログラムの書き方を強制（矯正？）されるというのが好きになれません。