次へ: リストを用いた再帰, 前へ: ロボットの製作：メタファーの拡張, 上へ: 再帰   [目次][索引]

11.3.2 再帰的定義の構成要素 ¶

再帰関数には通常、3つの部分からなる条件式が含まれています。

1. 関数が再度呼び出されるかどうかを判定する真偽値テストで、ここではdo-again-testと呼ぶ。
2. 関数の名前。この名前が呼び出されると、その関数の新しいインスタンス――いわば新しいロボット――が生成され、何をすべきか指示されます。
3. 関数が呼び出されるたびに異なる値を返す式で、ここではnext-step-expressionと呼ばれます。その結果、関数の新しいインスタンスに渡される引数（または複数の引数）は、前のインスタンスに渡されたものとは異なります。これにより、条件式であるdo-again-testは、正しい回数の繰り返しの後にfalseと判定されます。

再帰関数は、他のいかなる種類の関数よりもはるかに単純な場合があります。実際、使い始めたばかりの頃は、不可解なほど単純に見え、理解しがたいと感じることがよくあります。自転車に乗るのと同様に、再帰関数の定義を読み解くにはある程度のコツが必要で、最初は難しく感じられますが、やがて簡単に思えるようになります。

一般的によく見られる再帰パターンはいくつかあります。非常にシンプルなパターンは、次のようなものです。

(defun name-of-recursive-function (argument-list)
  "documentation..."
  (if do-again-test
    body...
    (name-of-recursive-function
         next-step-expression)))

再帰関数が評価されるたびに、その新しいインスタンスが生成され、何をすべきかが指示されます。引数によって、そのインスタンスに何をすべきかが伝えられます。

引数はnext-step-expressionの値に束縛されます。各インスタンスは、それぞれ異なるnext-step-expressionの値で実行されます。

next-step-expressionの値は、do-again-testで使用されます。

next-step-expression が返す値は関数の新しいインスタンスに渡され、そこで評価（あるいは何らかの変換）が行われることで、処理を継続するか停止するかが判定されます。next-step-expression は、関数をこれ以上繰り返すべきでない場合に、do-again-test が false を返すように設計されています。

やり直しテストは、偽と判定された時点で繰り返しを停止するため、停止条件と呼ばれることもある。