手続き本体は他の手続きへの呼び出しを含むことができます。 特別な場合には自分自身への呼び出しになります。
(define factorial (lambda (n) (if (= n 0) 1 (* n (factorial (- n 1))))))
この再帰的手続きは、ある数の階乗を計算するものです。
与えられた数が0
なら、答は1
です。それ以外のn
であれば、
この手続きは、n - 1
の階乗を自分自身をつかって計算し、その
途中の答とn
をかけて、その積を結果として返します。
相互に再帰する手続きを定義することも可能です。以下の奇遇性を チェックする述語は互いに再帰しています。
(define is-even? (lambda (n) (if (= n 0) #t (is-odd? (- n 1))))) (define is-odd? (lambda (n) (if (= n 0) #f (is-even? (- n 1)))))
ここにあげたのは極く単純な相互再帰の説明のためだけのものです。
Schemeではeven?
とodd?
はプリミティブ述語として既に用意されて
います。
letrec
上の手続きをローカル変数として手に入れたくなったら、
let
フォームを使って、
(let ((local-even? (lambda (n) (if (= n 0) #t (local-odd? (- n 1))))) (local-odd? (lambda (n) (if (= n 0) #f (local-even? (- n 1)))))) (list (local-even? 23) (local-odd? 23)))
とすることが可能かもしれません。しかし、これはうまく動きません。
初期化部のlocal-even?
とlocal-odd?
の出現はそれぞれのレキシカル
変数自身を参照しないからです。let
をlet*
に変更しても、やはり、
うまく動きません。local-odd?
本体の中のlocal-even?
は正しい値を
参照していますが、local-even?
中のlocal-odd?
はあいかわらず、
どこか他を指しているのです。
問題を解決するにはこんなふうに、Schemeの提供するフォーム
letrec
を利用します。
(letrec ((local-even? (lambda (n) (if (= n 0) #t (local-odd? (- n 1))))) (local-odd? (lambda (n) (if (= n 0) #f (local-even? (- n 1)))))) (list (local-even? 23) (local-odd? 23)))
letrec
によって導入されたレキシカル変数は、letrec
本体から
だけではなく、すべての初期化部からも見えています。というわけで、
letrec
は再帰的および相互再帰的ローカル手続きの定義にはもってこいです。
let
letrec
を用いて定義された再帰的手続きでループを表現することがきます。
たとえば、10
からのカウントダウンを表示したいとしましょう。
(letrec ((countdown (lambda (i) (if (= i 0) 'liftoff (begin (display i) (newline) (countdown (- i 1))))))) (countdown 10))
これはコンソールに10
から1
までの数字を出力し結果として
liftoff
を返します。
Schemeで名前つきlet
というのがあって、よりコンパクトに
このてのループを書くことができます。
(let countdown ((i 10)) (if (= i 0) 'liftoff (begin (display i) (newline) (countdown (- i 1)))))
let
の直後にあるループを識別する変数の存在に注意してください。
このプログラムはletrec
で書いたものと同等です。名前つきlet
は
letrec
フォームに展開されるマクロ(8章参照)のひとつである
と考えてさしつかえありません。
上で定義したcountdown
は実際には再帰的手続きです。
Schemeではループは再帰を通じてのみ定義することができます。
ループや反復をあつかう特別な構成はありません。
とは言っても、上で定義したようなループは真性のループです。 まちがいなく、ほかの言語での勘定と同じになっています。 どういうことかというと、Schemeは上のようなタイプの再帰には 特別に注意していて、手続きの呼び出し/復帰のオーバヘッドが 発生しないようにしています。
Schemeではこれを末尾呼び出しの除去と呼ばれている処理に
よって行います。countdown
手続きをよく見ると、countdown
本体中の
再帰的呼び出しがおこるときには、それが末尾呼び出しになっている
あるいは、まさに終るところとなっていることに気づくでしょう。
countdown
のおのおのの呼び出しが、自分自身を呼び出さないか、あるいは
呼び出すときには最後のアクションとして呼び出すかのどちらかです。
Schemeの実装にとってはこれは反復と区別がつかない再帰です。
というわけで、ループを再帰で書きましょう。安全です。
有用な末尾再帰的手続きのもうひとつの例です。
(define list-position (lambda (o l) (let loop ((i 0) (l l)) (if (null? l) #f (if (eqv? (car l) o) i (loop (+ i 1) (cdr l)))))))
list-position
はリストl
の中のオブジェクトo
が最初に出現する
インデックスを見つけます。見つからなければ、この手続きは#f
を返します。
さらにもうひとつ末尾再帰的手続きの例です。引数のリストの反転を「その場で」 やる手続きです。つまり、あらたに場所を確保せず、既存のリストの中身を 変更するということです。
(define reverse! (lambda (s) (let loop ((s s) (r '())) (if (null? s) r (let ((d (cdr s))) (set-cdr! s r) (loop d s))))))
(reverse!
はよくつかう手続きなので多くのScheme方言では、
プリミティブ手続きとして提供されています。MzScheme や Guile (や Gauche)
などです。)
数値計算での再帰(反復を含む)の例については付録 Cを参照 してください。
特別な反復はリストの各エレメントに対して同じアクションを繰り返すというの
があります。Scheme ではこうした状況用にふたつの手続きを用意しています。
map
とfor-each
です。
map
手続きは与えられた手続きを与えられたリストの各要素に
適用して、結果のリストを返します。たとえば、
(map add2 '(1 2 3)) => (3 4 5)
for-each
手続きも同様にリストの各要素に手続きを適用しますが、
なにも返しません。この手続き適用は純粋に副作用だけのためにあります。
たとえば、
(for-each display (list "one " "two " "buckle my shoe"))
はコンソールに文字列を(でてきた順に)表示する副作用があります。
map
およびfor-each
が適用する手続きは一引数の手続きである必要は
ありません。たとえば、n
引数の手続きがあたえられた場合にはmap
は
n
本のリストをとり、その手続きをそれぞれのリストから選ばれた
n
個の引数に適用します。たとえば、
(map cons '(1 2 3) '(10 20 30)) => ((1 . 10) (2 . 20) (3 . 30)) (map + '(1 2 3) '(10 20 30)) => (11 22 33)