前へ: 1または2の引数, 上へ: カウンタの代わりに再帰を用いる   [目次][索引]

3つか4つの論拠 ¶

triangle-recursively を引数 3 で呼び出したとします。

ステップ 1   再試行テストを評価する。

まず if 式が評価されます。これは do-again テストであり、false を返すため、if 式の else 部分が評価されます。（なお、この例では、do-again テストは true と判定されたときではなく、false と判定されたときに関数自身を呼び出す点に注意してください。）

ステップ 2   else部の最内式を評価する。

else部の最内表現が評価され、3が2にデクリメントされます。これが次のステップの式となります。

ステップ 3   triangle-recursively 関数を評価する。

数値2がtriangle-recursively関数に渡されます。

Emacsが引数2でtriangle-recursivelyを評価した際に何が起こるかは、すでに分かっています。前述の一連の処理を経て、3という値が返されます。したがって、ここでも同様の結果になります。

ステップ 4   足し算の結果を確認します。

3は加算の引数として渡され、関数が呼び出された際の数値である3に加算されます。

関数全体として返される値は6になります。

triangle-recursively を引数 3 で呼び出したときに何が起こるかが分かったので、引数 4 で呼び出したときに何が起こるかも明らかです：

再帰呼び出しにおいて、の評価

(triangle-recursively (1- 4))

評価結果を返します

(triangle-recursively 3)

これは6であり、この値は3行目の加算によって4に加算されます。

関数全体として返される値は10になります。

triangle-recursivelyが評価されるたびに、より小さな引数を用いて自身のバージョン――すなわち別のインスタンス――を評価し、引数が自身を評価しなくなるほど十分に小さくなるまでこれを繰り返します。

なお、再帰関数におけるこの特定の設計では、処理を遅延させる必要がある点に注意してください。

(triangle-recursively 7)が答えを算出する前には(triangle-recursively 6)を呼び出す必要があり、(triangle-recursively 6)が答えを算出する前には(triangle-recursively 5)を呼び出す必要があり、以下同様である。すなわち、(triangle-recursively 7)が行う計算は(triangle-recursively 6)が計算を行うまで延期されなければならず、(triangle-recursively 6)は(triangle-recursively 5)が完了するまで延期されなければならず、以下同様である。

これらのtriangle-recursivelyの各インスタンスをそれぞれ異なるロボットと見なすと、1台目のロボットは2台目が作業を終えるのを待たなければならず、2台目は3台目が作業を終えるのを待たなければならず、以下同様に続く。

こうした待機を回避する方法があり、それについてはDefermentを使わない再帰で解説します。