Lisp Scheme

[Lisp] 末尾再帰ってなんだ

「プログラミングGauche」を読んでいます。 (書籍はもう売っていないので、PDF版をオライリーから購入しました) Lispの勉強の為に読んでいるのですが、再帰処理の書き方も2パターンあって末尾再帰と非末尾再帰とあるそうです。 練習問題を解いた時の自分の解答例が非末尾再帰になっていたのですが、末尾再帰の方が有利な場合が多いとの事です。 ## リストの長さを計算するlengthをfoldを使わずに定義する ### 非末尾再帰パターン ```lisp `gutter:true; (define (length lis) (if (null? lis) 0 (+ 1 (length (cdr lis))))) ``` 最後の処理で再帰呼び出しの結果に対して足し算をしています。 ### 末尾処理パターン ```lisp `gutter:true; (define (length lis) (define (length-rec lis n) (if (null? lis) n (length-rec (cdr lis) (+ 1 n)))) (length-rec lis 0)) ``` length-recを定義する事で、末尾再帰にしています。 末尾再帰は再帰呼び出しの最後の呼び出し結果がそのまま上に伝版するパターンです。 そういった事も意識して続きを読み進めたいと思います。