再帰

手続き本体は他の手続きへの呼び出しを含むことができます。 特別な場合には自分自身への呼び出しになります。

(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?はプリミティブ述語として既に用意されて います。

6.1  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?の出現はそれぞれのレキシカル 変数自身を参照しないからです。letlet*に変更しても、やはり、 うまく動きません。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は再帰的および相互再帰的ローカル手続きの定義にはもってこいです。

6.2  名前つき 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で書いたものと同等です。名前つきletletrecフォームに展開されるマクロ(8章参照)のひとつである と考えてさしつかえありません。

6.3  反復

上で定義した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を参照 してください。

6.4  手続きのリスト上への写像

特別な反復はリストの各エレメントに対して同じアクションを繰り返すというの があります。Scheme ではこうした状況用にふたつの手続きを用意しています。 mapfor-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引数の手続きがあたえられた場合にはmapn本のリストをとり、その手続きをそれぞれのリストから選ばれた 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)