末尾再帰って言葉をはじめてきいたのがいつだったかよく覚えていませんが、最初の印象は「理解できるけどあたまにはいらない」でした。

今日なんとなく気が向いて、末尾再帰についてあらためて確認してみました。

まず何も考えずに、数字のリストの内容を素朴に足すsum1を定義してみます。

gosh>(define (sum1 lst)
(cond
((null? lst) 0)
(else (+ (car lst) (sum1 (cdr lst))))))
sum1
gosh>(sum1 '(1 2 3 4 5 6 7 8 9 10))
55
gosh>

これがわたしの思う、素直な再帰です。で、末尾再帰にはなっていません。再帰的に呼ばれたsum1の値は、一個上のレベルで(car lst)と加算されるからです。

では、これを末尾再帰にするとどうなるでしょう。

gosh>(define (sum2 lst)
(sum2-loop lst 0))
sum2
gosh> (define (sum2-loop lst n)
(cond
((null? lst) n)
(else (sum2-int (cdr lst) (+ n (car lst))))))
sum2-loop
gosh> (sum2 '(1 2 3 4 5 6 7 8 9 10))
55

sum2自体は、末尾再帰になっているsum2-loopを呼び出すだけです。sum2-loopでは末尾再帰にするために、ワークエリアになる引数「n」を用意しました

再帰で呼ばれるたびに、第２引数に値が足されていきます。最終的にリストが空になったら、その第2引数をそのままかえす。

...久しぶりに末尾再帰の概念を確認してみました。やっぱりこれ、ループの表現変えただけじゃん。戻り値を保持するための引数ってかっこわるいじゃん。ループと等価だからループに最適化できる、って見るからにあたりまえじゃん(最適化の実装はあたりまえ、じゃないだろうけど)。再帰な問題を再帰でかく喜びというか驚きがかんじられないじゃん。

と、あらためて思いました。

しかし、わたしは間違っていた、末尾再帰(的なモデルの意義)の神髄の片鱗を、きょうはじめて実感できたかも! と思ったのでした。

以下次号。