呼称: リストの末尾再帰呼び出し
目的: 2種類の再起呼び出しがあることを学ぶ
備考: 末尾再帰の方が、効率が良い場合が多いので推奨
第6章のリストを勉強するのに4回(4日)費やしてしまいました。ページ数は20ページ弱です。それだけ私にとっては難しかったです。まだまだ理解できているとは言えないけど、少しおもしろくなってきました。
処理の一番最後の再起呼び出しをして、その結果がそのまま現在の処理の結果として返されるパターンを末尾再帰と呼びます。
昨日の Gauche のリスト処理手続き : 3 の練習問題で、リストの長さを計算する length2 が末尾再起で、条件を満たす要素のリストを作成する filter がそうではないパターンの処理です。
Scheme では、最後に呼び出した手続きの戻り値に何も行わない場合、最後の呼び出しは通常の意味の手続き呼び出しではなくジャンプとして扱われることになっています。これはプログラムコード上では再起「呼び出し」として書いてあっても、実質的にはループとして実行されるということを意味します。
さらに昨日の reverse2 を末尾再帰にしてみます。reverse3 は fold を使って末尾再帰にしたものです。reverse4 は、さらに fold の定義も書いたものです。ローカル手続き reverse4-rec は初期値 init が自明なので、引数を減らすために定義しています。
(define (reverse3 lis) (fold cons '() lis)) (define (reverse4 lis) (define (reverse4-rec init lis) (if (null? lis) init (reverse4-rec (cons (car lis) init) (cdr lis)))) (reverse4-rec '() lis))
実行結果。
gosh> (reverse3 '(1 2 3)) (3 2 1) gosh> (reverse4 '(1 2 3 4.5)) (4.5 3 2 1)
