3. その結果を表示する
3.11 再帰
された場合を考えましょう。上の例で変数xが数ではなくて記号だったら、引数評価のと
き、(+ x 1) の評価をしようとして、記号に
1
を加えることになってエラーになります。特殊形式orは一般に、
} (or h式1i
h式2i
...
h式
n
i)の形をしています。特殊形式or の実行は次のようになります。まず h式1
i を評価します。
もし評価結果が偽#f ならば 、次の式 h式2iを評価します。同様にして、評価結果が偽 #f ならばさらに次の式を評価します。これを評価結果が偽である限り続けてゆきます。もし 最後まで評価結果が偽なら、orの値として偽が返されます。もし途中で評価結果が偽以外 のものがあれば or の実行を終了し 、その評価結果が or の値として返されます。or も単 なる論理和を計算するのではないことに注意しましょう。
例を見てみましょう。
> (define x -20)
#<unspecified>
> (if (or (< x 0) (> x 100)) "x < 0 or 100 < x" "else")
"x < 0 or 100 < x"
変数 x の値は -20なので、この例では (< x 0)が真となり、この値が or の値として返 されます。
> (if (or (= x 0) (> x 0)) "x >= 0" "x < 0")
"x < 0"
この例では、orに現れるどの式も評価結果が偽なのでor の値は#fとなり、ifにより "x
< 0"が返されています。
の
DO
文に似た、ループのための構文がScheme
にも用意されています。興味がある人は10.1.1
を参照して下さい。再帰
(recursion)
は、Scheme
での繰り返し実行のための基本的な概念です。次に示す階乗の計算をする手続き factを見てください。
(define (fact n) (if (= n 0)
1
(* n (fact (- n 1)))))
階乗は
1
からn
までの全ての整数をかけあわせたものです。すなわち、 定義はn ! = 1
2
( n
,1)
n
となっています。(fact 4)が上の手続きによってどのように計算され るか、計算過程を見てみましょう。(fact 4)
) (* 4 (fact 3))
) (* 4 (* 3 (fact 2)))
) (* 4 (* 3 (* 2 (fact 1))))
) (* 4 (* 3 (* 2 (* 1 (fact 0)))))
) (* 4 (* 3 (* 2 (* 1 1))))
) (* 4 (* 3 (* 2 1)))
) (* 4 (* 3 2))
) (* 4 6)
) 24
これをわかりやすい形で書けば 、
(fact 4)は
4
に (fact 3)をかけたもの.
(fact 3)は
3
に (fact 2)をかけたもの.
(fact 2)は
2
に (fact 1)をかけたもの.
(fact 1)は
1
に (fact 0)をかけたもの.
(fact 0)は
1
である.
よって (fact 1)は
1
1 = 1
である.
よって (fact 2)は
2
1 = 2
である.
よって (fact 3)は
3
2 = 6
である.
よって (fact 4)は
4
6 = 24
である.
という過程で計算されています。
このようにある手続きが計算するのに 、さらにその手続き自身を呼び 出す方法を再帰
(recursion)
といいます21。別の例として、リストの長さを求める手続きを作ってみましょう。リスト
l
の長さは 、次のようにして定義されます。
l
が空リストなら、l
の長さは0
です。そうでなければ 、(cdr
l
) の長さに1
加えたものが 、l
の長さです。これを手続きにすると、次のようになります。
(define (len l) (if (null? l)
0
(+ (len (cdr l)) 1)))
この定義によると、lが空リストでないときは (cdr l)を引数として、再帰的に呼び出し をしています。ですが再帰呼び出しのたびにl は短いリストになってゆきますので、いつ かは空リストになり、(null? l) の条件が満たされます。そのため、再帰呼び出しが永 遠に繰り返されることはありません。
ではもういちど 階乗を計算する手続きfactを見てみましょう。この計算法で (fact
n
)の計算をするのに、(fact
n
,1
) の計算を終了した後にその計算結果とn
をかけるようになっています。ですので、(fact
n
,1
)の計算した後にまた戻ってきてn
をかけないといけない、ということを覚えておく必要があります。この計算法では再帰呼び出しをする たびに、戻ってきた後にすべき仕事を記憶する必要があります。(fact 5)の計算過程で括 弧の入れ子が深くなってゆくのはこのためです。このことは、実行のために多くの記憶領 域を必要とすることを意味します。
階乗の計算は単に
1
からn
までを順々にかけ合わせればいいので、あとでn
をかける、という「戻り情報」は覚えなくてもよいはずです。この考えに基づいた計算方法による階 乗計算をする手続き fact2 の定義を示します。
(define (fact2 n)
(define (fact-sub n f) (if (= n 0)
f
(fact-sub (- n 1) (* f n)))) (fact-sub n 1))
21手続き fが直接それ自身を呼び出さずに、別の手続きを gを呼び出し 、gが fを呼び出す場合も再帰 といいます。このような場合は特に、相互再帰
(mutual recursion)
といいます。(fact2 4)の計算過程は、次のようになります。
(anonther-fact 4)
) (fact-sub 4 1)
) (fact-sub 3 4)
) (fact-sub 2 12)
) (fact-sub 1 24)
) (fact-sub 0 24)
) 24
fact2の内部で定義されている手続き fact-subでは、その第
1
引数 nが0
以外であれば 、再帰的にfact-sub を呼び出しています。ですが呼び出し側は、再帰呼び出しで得ら れた値を別の手続きの引数にすることはせず、呼び出した手続きの値をそのまま計算結果 として返しています。このために、再帰呼び出しされた手続きは計算結果を持って呼出し 側に戻る必要はありません。
Scheme
では 、このような場合には「呼び出し 」の代わりに「分岐」を使い、戻り情報を保持しないようにしています。
fact2のように、 プログラムの文面上では手続きの再帰呼び出しでも、実際の手続き呼
び出しの際には「分岐」がおこなわれます。そのため、戻り情報を記憶しないので、
n
の値に関わらず、一定の記憶領域しか必要としません。
手続き呼び出しがあるたびにプログラムの戻り場所をスタック
(stack)
と呼ばれる記憶場所に蓄 えます。手続きの実行が終了したら戻る場所をスタックから取り出し 、計算結果を持って戻り場所 に分岐します。そのため手続きの中でさらに手続きを呼び出すと、スタックにはどんどん戻り場所 情報が蓄積されます。これは記憶領域をどんどん消費してゆくことを意味します。ですがある手続 き fがその中で手続き gを呼び出していて、gの返す値をそのまま fの値として返す場合を考え ましょう。gを呼び出すときに戻り場所をスタックに蓄えず、実行を gに移します。gが終了する ときにスタックから取り出される戻り場所は、fの呼び出しに対する戻り場所となります。このた めgが終了すると fに戻ることはなく、fの呼び出しに対する戻り場所に戻ることになります。し かも得られた値は、戻り情報をすべてスタックに蓄えていたときとまったく同じです。このように 他の手続きを呼び出しその計算結果をそのまま返す場合は、戻り情報を保持しないことでスタック の使用(
記憶領域の消費)
をしなくて済みます。このため手続き factの実行には、引数
n
に比例した数の戻り情報をスタックに保持する必要 があります。(
再帰の入れ子が一番深い時にもっとも多くのスタックを使います。)
いっぽ う手続きfact2では、評価のときに使う作業領域は引数の値とは関係なく、一定の領域しか使いません。こ
のような性質は末尾再帰的
(tail recursive)
であると呼ばれます。このことを分かりやすい例で説明すれば 、次のようになります。あなたはある町工場で働いてい る社員だとしましょう。
A
社から依頼されたある機械の製作を、下請けのB
社に依頼したとします。ある日、
B
社から機械が完成したとの依頼を受けました。製品検査や機械の調整が必要なら、B
社に機械を受け取りに行き、自分の会社に運び 、そしてA
社に納品することになります。とこ ろがあなたがB
社の技術を信用していて製品検査は必要ないと思えば 、わざわざ 自分の会社に運 ぶ必要はありません。B
社に機械を受け取りに行き、その足で直接A
社に納品すればいいでしょ う。営業担当の人が、得意先廻りで夜になったときに、特に何もなければ会社に戻らずそのまま自宅に帰ったりします。ここでも無意識のうちに「末尾再帰」の考えが使われています。