11. ループと再帰

Emacs Lispには、式や一連の式を繰り返し評価する主要な方法が2つあり、 whileループを使う方法と再帰（recursion）を使う方法である。

繰り返しはとても重要である。 たとえば、4つの文だけ先へ進むには、 1つの文のみ先へ進むだけのプログラムを書き、それを4回繰り返せばよい。 人間は繰り返し回数をまちがえたり処理を誤ったりするが、 コンピュータが飽きたり疲れたりすることはないので、 繰り返し動作が有害な結果を生むことはない。

11.1 while

スペシャルフォームwhileは、第1引数を評価した結果が真か偽かを検査する。 これは、Lispインタープリタがifに対して行うことに似ているが、 その検査後にインタープリタが行うことは異なる。

while式では、第1引数を評価した結果が偽ならば、 Lispインタープリタは式の残りの部分（式の本体）を飛び越し、 それらを評価しない。 しかし、値が真ならば、Lispインタープリタは式の本体を評価し、 再度、第1引数が真か偽かを検査する。 第1引数を再度評価した結果が真ならば、 Lispインタープリタは式の本体を再度評価する。

while式の雛型はつぎのとおりである。

(while 判定条件
  本体...)

評価したときにwhile式の判定条件が真を返す限り、 本体を繰り返し評価する。 飛行機が旋回（ループ）するように、Lispインタープリタが同じことを 何度も何度も繰り返すので、この処理をループと呼ぶ。 判定条件の評価結果が偽ならば、Lispインタープリタはwhile式の 残りを評価せず「ループから出る」。

明らかに、whileの第1引数の評価結果がつねに真ならば、 それに続く本体は何度も何度も...何度も...永久に評価される。 逆に、評価結果がけっして真にならなければ、本体の式はけっして評価されない。 whileループを書く工程は、続く式を評価したい回数だけ真を返し、 そのあとは偽を返すような判定条件を選ぶことである。

whileを評価した結果返される値は、判定条件の値である。 この帰結として興味深いことは、エラーなしに評価されるwhileループは、 1回繰り返そうが100回繰り返そうがまったく繰り返さなくても、 nil、つまり、偽を返すことである。 正しく評価できたwhile式は、けっして真を返さない！　 つまり、whileはつねに副作用のために評価されるのであり、 whileループの本体の式を評価した効果だけのためである。 これは意味のあることである。 ほしいのは単なる繰り返し動作ではなく、 ループの式を繰り返し評価したときの効果がほしいのである。

11.1.1 whileループとリスト		A while loop that uses a list.
11.1.2 例：print-elements-of-list		Uses while, car, cdr.
11.1.3 増加カウンタによるループ		A loop with an incrementing counter.
11.1.4 減少カウンタによるループ		A loop with a decrementing counter.

11.1.1 whileループとリスト

whileループを制御する一般的な方法は、 リストに要素があるかどうかを検査することである。 要素があればループを繰り返すが、要素がなければ繰り返しを終える。 これは重要な技法なので、例示のために短い例を作ることにする。

リストに要素があるかどうかを検査する簡単な方法は、 リストを評価することである。 要素がなければ、空リストであるから空リスト()が返され、 これは偽を意味するnilの同義語である。 一方、リストに要素があれば、評価するとこれらの要素を返す。 Lispインタープリタは、nil以外の値を真と解釈するので、 要素を返すリストはwhileループの検査では真になる。

たとえば、つぎのsetq式を評価すれば、 変数empty-listにnilを設定できる。

(setq empty-list ())

setq式を評価しておけば、いつものようにシンボルの直後に カーソルを置いてC-x C-eとタイプすれば変数empty-listを 評価できる。 エコー領域にはnilと表示される。

empty-list

一方、つぎの2つの式を評価するとわかるように、 要素を持つリストを変数に設定して、その変数を評価するとリストが表示される。

(setq animals '(giraffe gazelle lion tiger))

animals

したがって、リストanimalsに要素があるかどうかを検査する whileループを書くと、ループの始めの部分はつぎのようになる。

(while animals
       ...

whileが第1引数を検査するとき、変数animalsが評価される。 これはリストを返す。 リストに要素がある限り、whileは検査結果は真であると解釈する。 しかし、リストが空になると検査結果は偽であると解釈する。

whileループが永久に廻り続けるのを防ぐには、 最終的にリストが空になるような機構を与える必要がある。 しばしば使われる技法は、while式の中の式の1つで、 リストの値にリストのCDRを設定することである。 関数cdrを評価するたびに、リストは短くなり、最終的には空リストになる。 その時点でwhileループの検査は偽を返し、 whileの引数はそれ以上評価されなくなる。

たとえば、つぎの式で、動物のリストを束縛した変数animalsに もとのリストのCDRを設定できる。

(setq animals (cdr animals))

まえの式を評価してからこの式を評価すると、 エコー領域に(gazelle lion tiger)と表示される。 この式を再度評価すると、エコー領域に(lion tiger)と表示される。 さらに評価すると(tiger)となり、 さらに評価すると空リストになりnilと表示される。

関数cdrを繰り返し使って最終的に判定条件が偽になるような whileループの雛型はつぎのようになる。

(while リストが空かどうか検査
  本体...
  リストのcdrをリストに設定)

この検査とcdrの利用は、 リスト全体を調べてリストの各要素を1行に表示する関数で使える。

11.1.2 例：print-elements-of-list

関数print-elements-of-listはリストを用いたwhileループの例である。

この関数は、複数行出力する。 エコー領域は1行分のみなので、これまでの関数の動作例を示すようには Infoの中で評価して動作を示すことができない。 かわりに、式をバッファ`*scratch*'にコピーしてから、 そのバッファで評価する必要がある。 式をコピーするには、 リージョンの始めをC-SPC（set-mark-command）で マークし、カーソルをリージョンの終わりに移動してから、 M-w（copy-region-as-kill）を使ってリージョンをコピーする。 つぎに、バッファ`*scratch*'にて、 C-y（yank）とタイプすればその式を取り出せる。

バッファ`*scratch*'に式をコピーしてから、各式を順番に評価する。 最後の式(print-elements-of-list animals)は、必ず、 C-u C-x C-eとタイプして、つまり、 eval-last-sexpに引数を与えて評価すること。 これにより、評価結果は、エコー領域ではなく、 バッファ`*scratch*'に表示される （さもないと、エコー領域には、^Jgiraffe^J^Jgazelle^J^Jlion^J^Jtiger^Jnil のように表示される。 ここで、`^J'は改行のことであり、 バッファ`*scratch*'で1行に1語ずつ表示する。 これらの式をInfoバッファで評価すれば、この効果を見ることができる）。

(setq animals '(giraffe gazelle lion tiger))

(defun print-elements-of-list (list)
  "Print each element of LIST on a line of its own."
  (while list
    (print (car list))
    (setq list (cdr list))))

(print-elements-of-list animals)

バッファ`*scratch*'で3つの式を順番に評価すると、 バッファにはつぎのように表示される。

giraffe

gazelle

lion

tiger

nil

リストの各要素が（関数printの動作により）1行に表示され、 最後に関数が返した値が表示される。 関数の最後の式はwhileループであり、whileループはつねにnil を返すので、リストの最後の要素のあとに、nilが表示される。

11.1.3 増加カウンタによるループ

終了すべきときに止まらないループは無意味である。 ループをリストで制御する以外に、ループを止める一般的な方法は、 必要回数の繰り返しを完了したら偽を返すような第1引数を書くことである。 つまり、ループにカウンタ、ループの繰り返し回数を数える式 を持たせるのである。

(< count desired-number)のように判定条件を記述すれば、 countの値が繰り返し回数desired-numberより小さければ真を返し、 countの値がdesired-numberに等しいか大きければ偽を返す。 カウンタを増加させる式は(setq count (1+ count))のような 簡単なsetqでよく、1+は引数に1を加えるEmacs Lispの 組み込み関数である （式(1+ count)は、(+ count 1)と同じ結果をもたらし、 人間にも読みやすい）。

カウンタを増加して制御するwhileループの雛型はつぎのようになる。

カウンタに初期値を設定
(while (< count desired-number)         ; 判定条件
  本体...                    
  (setq count (1+ count)))              ; 1増やす

countの初期値を設定する必要があることに注意してほしい。 普通は1に設定する。

増加カウンタの例		Counting pebbles in a triangle.
関数定義の各部分		The parts of the function definition.
関数定義をまとめる		Putting the function definition together.

増加カウンタの例

浜辺で遊んでいるときに、つぎに示すように、 最初の行には小石を1個、つぎの行には2個、そのつぎの行には3個というように、 小石で三角形を作ろうと考えたとする。

               *
              * *
             * * *
            * * * *

（約2500年前に、ピタゴラスや他の人達は、 このような問題を考察して数論の始まりを築いた。）

7行の三角形を作るには何個の小石が必要か知りたいとしよう。

明らかに、必要なことは数1から7までを加算することである。 これには2つの方法がある。 最小数1から始めて、1、2、3、4のように加算する。 あるいは、最大数から始めて、7、6、5、4のように加算する。 いずれの方法も、whileループを書く一般的な方法の例示になるので、 増やしながらの加算と減らしながらの加算の2つの例を書くことにする。 まずは、1、2、3、4と加算する例から始める。

数個の数を加算するだけならば、もっとも簡単な方法は、 それらをいっきに加算することである。 しかし、あらかじめ何個の数を加算するかわかっていなかったり、 非常に多くの数の加算にも対処したければ、 複雑な処理をいっきに行うのではなく、 単純な処理を繰り返すような加算にする必要がある。

たとえば、小石の個数をいっきに加算するかわりに、 最初は1行目の小石の個数1を2行目の個数2に加え、 これらの総和を3行目の個数3に加える。 つぎに、4行目の個数4を1行目から3行目までの総和に加えるということを繰り返す。

処理の重要な点は、繰り返しの各段階の動作は単純であることである。 この例では、各段階では、2つの数、つまり、 その行の小石の個数とそれまでの総和を加算するだけである。 最後の行をそれまでの総和に加算するまで、 2つの数の加算処理を繰り返し繰り返し実行するのである。 より複雑なループでは、各段階の動作は単純ではないかもしれないが、 すべてをいっきに行うよりは簡単である。

関数定義の各部分

以上の分析により、関数定義の骨格がわかる。 まず、小石の総数を保持する変数totalが必要である。 これは、関数が返す値である。

つぎに、関数には引数が必要である。 この引数は三角形の行数である。 これをnumber-of-rowsとしよう。

最後に、カウンタとして使う変数が必要である。 この変数をcounterと命名してもよいが、 より適したrow-numberを使おう。 カウンタが数えるのは行数であり、 プログラムではできる限りわかりやすい名前を使うべきだからである。

Lispインタープリタが関数内の式の評価を始めるときには、 totalには何も加算していないので、 totalの値は0になっているべきである。 続いて、関数では、1行目の小石の個数を総和に加算し、 2行目の小石の個数を総和に加算し、3行目の小石の個数を総和に加算し、 ということを、加算すべき行がなくなるまで行う。

totalとrow-numberのどちらも、関数の内部だけで使うので、 letでローカル変数として宣言し初期値を与える。 明らかに、totalの初期値は0である。 また、第1行から始めるので、row-numberの初期値は1である。 つまり、let文はつぎのようになる。

  (let ((total 0)
        (row-number 1))
    本体...)

内部変数を宣言しそれらに初期値を束縛したら、whileループを始められる。 判定条件の式は、row-numberがnumber-of-rowsより小さいか等しい 限りは真を返す必要がある （行の番号が三角形の行数より小さい場合に限り真を返す判定条件だと、 最後の行が総和に加算されない。 したがって、行の番号は三角形の行数より小さいか等しい必要がある）。

Lispには、第1引数が第2引数より小さいか等しいときに真を返し、 それ以外のときには偽を返す関数<=がある。 したがって、whileが判定条件として評価する式はつぎのようになる。

(<= row-number number-of-rows)

小石の総数は、すでにわかっている総数に行の小石の個数を加算することを 繰り返して計算できる。 行の小石の個数はその行の番号に等しいので、 総数は、総数に行番号を加算すれば計算できる （より複雑な状況では、行の小石の個数は、より複雑な方法で行の番号に関係する。 そのような場合には、行の番号を適当な式で置き換える）。

(setq total (+ total row-number))

これにより、totalの新たな値は、行の小石の個数をそれまでの総数に 加えたものになる。

totalの値を設定したあと、 ループのつぎの繰り返しのための条件を確立する必要がある。 これには、カウンタとして働く変数row-numberの値を増やせばよい。 変数row-numberを増やしたあと、whileループの判定条件により、 その値がnumber-of-rowsより小さいか等しいかどうか検査する。 もしそうならば、変数row-numberの新たな値を ループのまえの段階でのtotalに加える。

Emacs Lispの組み込み関数1+は数に1を加えるので、 つぎの式で変数row-numberを増加できる。

(setq row-number (1+ row-number))

関数定義をまとめる

関数定義の各部分を作ったので、それらを1つにまとめよう。

まず、while式の内容はつぎのとおりである。

(while (<= row-number number-of-rows)   ; 判定条件
  (setq total (+ total row-number))
  (setq row-number (1+ row-number)))    ; 増加

let式の引数リストを加えれば、これで関数定義の本体はぼぼ完成する。 しかし、その必要性は少々微妙ではあるが、最後の要素が必要である。

つまり、while式のあとに、変数totalだけを置いた行が必要である。 さもないと、関数全体としての戻り値は、最後の式の値、 つまり、letの本体を評価した値、 つまり、whileが返す値であるが、これはつねにnilである。

一見しただけでは、これは自明ではないかもしれない。 関数全体としての最後の式は、増加する式であると思うだろう。 しかし、その式はシンボルwhileで始まるリストの最後の要素であり、 whileの本体の一部である。 さらに、whileループ全体も、letの本体の中にあるリストである。

関数の概略はつぎのとおりである。

(defun 関数名 (引数リスト)
  "説明文..."
  (let (変数リスト)
    (while (判定条件)
      whileの本体... )
      ... )                     ; 最後の式をここに置く

letは、defun全体としてのリスト以外のリストの内側にはないので、 letを評価した結果がdefunが返す値となる。 しかし、whileがlet式の最後の要素だったとすると、 関数はつねにnilを返す。 これは、われわれが望むことではない！　 変数totalの値を返したいのである。 それには、letで始まるリストの最後の要素として、 そのシンボルを書けばよい。 これにより、リストのまえのものが評価されたあとに、 正しい総数が設定されてから評価される。

このことは、letで始まるリストを1行に書くとわかりやすいであろう。 変数リストとwhile式は、letで始まるリストの 第2要素と第3要素であり、totalは最後の要素であることがはっきりする。

(let (変数リスト) (while (判定条件) whileの本体... ) total) 

以上をまとめると、triangleの関数定義はつぎのとおりである。

(defun triangle (number-of-rows)    ; 増加カウンタを利用した版
  "Add up the number of pebbles in a triangle.
The first row has one pebble, the second row two pebbles,
the third row three pebbles, and so on.
The argument is NUMBER-OF-ROWS."
  (let ((total 0)
        (row-number 1))
    (while (<= row-number number-of-rows)
      (setq total (+ total row-number))
      (setq row-number (1+ row-number)))
    total))

関数を評価してtriangleをインストールすれば、試すことができる。 2つの例をあげておく。

(triangle 4)

(triangle 7)

最初の4つの数を総和したものは10であり、最初の7つを総和したものは28である。

11.1.4 減少カウンタによるループ

whileループを書く一般的な別の方法は、 カウンタが0より大きいかを調べる検査を使うことである。 カウンタが0より大きい限り、ループを繰り返す。 しかし、カウンタが0になるか0より小さくなったら、ループを止める。 このように動作させるには、カウンタを0より大きく設定しておき、 繰り返すたびにカウンタを小さくするのである。

counterの値が0より大きければ真tを返し、 counterの値が0に等しいか小さければ偽nilを返す (> counter 0)のような式を判定条件に使う。 数を減らす式は、(setq counter (1- counter))のような単純なsetq でよく、1-は引数から1を引くEmacs Lispの組み込み関数である。

減算によるwhileループの雛型はつぎのようになります。

(while (> counter 0)                    ; 判定条件
  本体...
  (setq counter (1- counter)))          ; 1減少

減少カウンタの例		More pebbles on the beach.
関数の各部分		The parts of the function definition.
関数定義をまとめる		Putting the function definition together.

減少カウンタの例

減少カウンタによるループの例として、カウンタを0まで減少させるように 関数triangleを書き換える。

これは、この関数の前版の逆である。 つまり、3行の三角形を作るために必要な小石の個数は、 3行目の小石の個数3をそのまえの個数2に加え、2つの行の総数を そのまえの個数1に加えて計算する。

同様に、7行の三角形の小石の個数は、 7行目の小石の個数7をまえの行の個数6に加え、2つの行の総数を それらのまえの行の個数5に加え、と繰り返して計算する。 まえの例と同様に、各加算では2つの数、すでに加算した行の総数と、 加算すべき行の小石の個数を扱う。 2つの数を加える処理を、加えるべき小石がなくなるまで繰り返す。

始めの小石の個数はわかっている。 最後の行の小石の個数は、その行の番号に等しい。 7行の三角形の場合、最後の行の小石の個数は7である。 同様に、1つまえの行の小石の個数もわかっていて、行の番号より1つ小さい。

関数の各部分

3つの変数が必要である。 三角形の行の数、行の小石の個数、求めたい小石の総数である。 これらの変数をそれぞれ、number-of-rows、 number-of-pebbles-in-row、totalとしよう。

totalとnumber-of-pebbles-in-rowのいずれも関数の内側だけで 使うので、これらはletで宣言する。 totalの初期値は、当然、0である。 しかし、もっとも長い行から加算を始めるので、 number-of-pebbles-in-rowの初期値は、 三角形の行数に等しい必要がある。

つまり、let式の始めの部分はつぎのようになる。

(let ((total 0)
      (number-of-pebbles-in-row number-of-rows))
  本体...)

小石の総数は、行の小石の個数をすでにわかっている総数に加算すればよく、 つぎの式を繰り返し評価すればよい。

(setq total (+ total number-of-pebbles-in-row))

number-of-pebbles-in-rowをtotalに加算したあと、 ループのつぎの繰り返しでは、まえの行を総和に加算するので、 number-of-pebbles-in-rowを1減らす必要がある。

まえの行の小石の個数は、今の行の小石の個数より1小さいので、 Emacs Lispの組み込み関数1-を使って、まえの行の小石の個数を計算できる。 これはつぎの式になる。

(setq number-of-pebbles-in-row
      (1- number-of-pebbles-in-row))

whileループは行の小石がなくなったら繰り返しを止める。 したがって、whileループの判定条件は単純である。

(while (> number-of-pebbles-in-row 0)

関数定義をまとめる

以上の式をまとめると、つぎのような関数定義を得る。

;;; 最初の減算版
(defun triangle (number-of-rows)        
  "Add up the number of pebbles in a triangle."
  (let ((total 0)
        (number-of-pebbles-in-row number-of-rows))
    (while (> number-of-pebbles-in-row 0)
      (setq total (+ total number-of-pebbles-in-row))
      (setq number-of-pebbles-in-row
            (1- number-of-pebbles-in-row)))
    total))

この関数は正しく動作する。

しかし、1つのローカル変数number-of-pebbles-in-rowは、 不要であることがわかる。

関数triangleを評価するとき、 シンボルnumber-of-rowsには数が束縛され、それが初期値になる。 その数を変更しても関数の外側の変数の値に影響することはなく、 ローカル変数であるかのように関数の本体でその数を変更できる。 これはLispのとても有用な特徴である。 つまり、関数内部では、number-of-pebbles-in-rowのかわりに 変数number-of-rowsを使えるのである。

簡素に書き直した、この関数の第2版を示す。

(defun triangle (number)                ; 第2版
  "Return sum of numbers 1 through NUMBER inclusive."
  (let ((total 0))
    (while (> number 0)
      (setq total (+ total number))
      (setq number (1- number)))
    total))

まとめると、正しく書かれたwhileループは3つの部分から成る。

1. 必要回数だけループを繰り返したら偽を返す判定条件。

2. 繰り返し評価したあとに望みの値を返す式。

3. 必要回数だけループを繰り返したら判定条件が偽を返すように、 判定条件で使う値を変更する式。

11.2 再　帰

再帰的関数では、自分自身の評価を指示するコードを含む。 関数が自分自身を評価するとき、自分自身の評価を指示するコードを 再度みつけるので、関数は自分自身を再度評価する...を繰り返す。 再帰的関数は、停止条件が与えられない限り、 自身を評価することを永久に続ける。

典型的な再帰的関数には、3つの部分から成る条件式が含まれる。

1. 関数を再度呼び出すかどうかを決定する判定条件。 これを再帰条件（do-again-test）と呼ぶ。

2. 関数名。

3. 必要回数だけ繰り返したあとに条件式を偽にするような式。 これを次段式（next-step-expression）と呼ぶ。

再帰的関数は、他の種類の関数よりもとても簡単である。 もちろん、これを使い始めたばかりの人には、 理解できないほど不可思議に単純に見える。 自転車に乗るのと同じように、再帰的関数定義を読むには、 最初は難しくてもしだいに簡単に思えるようになるコツが必要である。

再帰的関数の雛型はつぎのようになる。

(defun 再帰的関数名 (引数リスト)
  "説明文..."
  本体...
  (if 再帰条件
    (再帰的関数名 
         次段式)))

再帰的関数を評価するたびに、引数には次段式の値が束縛され、 その値を再帰条件で使う。 関数をそれ以上繰り返さない場合には、再帰条件が偽になるように次段式を作る。

再帰条件が偽になると繰り返しを停止するので、 再帰条件を停止条件（stop condition）と呼ぶこともある。

11.2.1 リストについての再帰		Using a list as the test whether to recurse.
11.2.2 カウンタの代用としての再帰		Replacing a while loop with recursion.
11.2.3 condを用いた再帰の例		Recursion example with a different conditional.

11.2.1 リストについての再帰

動物のリストの各要素を表示するwhileループの例を 再帰的に書くことができる。 変数animalsにリストを設定する式も含めて、そのコードを示す。

この例は、バッファ`*scratch*'にコピーしてから、 そこで個々の式を評価する必要がある。 結果がバッファに表示されるように、C-u C-x C-eを使って 式(print-elements-recursively animals)を評価すること。 さもないと、Lispインタープリタは結果をエコー領域の1行に押し込めて表示する。

また、関数print-elements-recursivelyの注釈のまえの 最後の閉じ括弧の直後にカーソルを置くこと。 さもないと、Lispインタープリタは注釈を評価しようとする。

(setq animals '(giraffe gazelle lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (print (car list))                  ; 本体
  (if list                            ; 再帰条件
      (print-elements-recursively     ; 再帰呼び出し
       (cdr list))))                  ; 次段式

(print-elements-recursively animals)

関数print-elements-recursivelyは、まず、リストの先頭要素、 つまり、リストのCARを表示する。 続いて、リストが空でなければ、関数は自分自身を呼び出すが、 その引数には、リスト全体ではなく、リストの2番目以降の要素、 つまり、リストのCDRを渡す。

これを評価すると、受け取った引数（もとのリストの2番目以降の要素）の先頭要素を 表示する。 続いて、if式を評価し、真ならば、リストのCDR、 つまり、（2回目なので）もとのリストのCDRのCDRを 引数として自身を呼び出す。

関数が自身を呼び出すごとに、もとのリストを短くしたものを引数に渡す。 最終的に、空リストで自身を呼び出す。 関数printは空リストをnilと表示する。 つぎに、条件式ではlistの値を調べる。 listの値はnilなので、if式の判定条件は偽になり、 真の場合の動作は評価されない。 そして、関数全体としてはnilを返す。 そのため、この関数を評価するとnilが2つ表示されるのである。

バッファ`*scratch*'で(print-elements-recursively animals)を 評価するとつぎのようになる。

giraffe

gazelle

lion

tiger

nil

nil

（最初のnilは空リストの値を表示したもので、 2番目のnilは関数全体としての戻り値である。）

11.2.2 カウンタの代用としての再帰

前節で説明した関数triangleを再帰で書くこともできる。 つぎのようになる。

(defun triangle-recursively (number)
  "Return the sum of the numbers 1 through NUMBER inclusive.
Uses recursion."
  (if (= number 1)                    ; 再帰条件
      1                               ; 真の場合の動作
    (+ number                         ; 偽の場合の動作
       (triangle-recursively          ; 再帰呼び出し
        (1- number)))))               ; 次段式

(triangle-recursively 7)

これを評価して関数をインストールすれば、 (triangle-recursively 7)を評価して試すことができる （注釈のまえの関数定義の最後の括弧の直後にカーソルを置くこと）。

この関数の動作を理解するために、 引数として、1、2、3、4をこの関数に渡すとどうなるかを考えよう。

まず、引数が1の場合はどうなるだろうか？

関数には、説明文字列に続けてif式がある。 これはnumberの値が1に等しいかどうかを調べる。 等しければ、Emacsはif式の真の場合の動作を評価し、 関数の値として数1を返す （1行の三角形には1個の小石がある）。

では、引数の値が2の場合を考えよう。 この場合は、Emacsはif式の偽の場合の動作を評価する。

偽の場合の動作は、加算、triangle-recursivelyの再帰呼び出し、 減算動作から成り、つぎのとおりである。

(+ number (triangle-recursively (1- number)))

Emacsがこの式を評価するとき、もっとも内側の式が最初に評価され、 つぎに、それ以外の部分が評価される。 詳しくはつぎのような手順になる。

手順1　もっとも内側の式を評価する。

もっとも内側の式は(1- number)であり、 Emacsはnumberの値を2から1へ減らす。

手順2　関数triangle-recursivelyを評価する。

関数の中にそれ自身があるかどうかは関係ない。 Emacsは手順1の結果を引数として使って、 関数triangle-recursivelyを呼び出す。

この場合、Emacsは引数1でtriangle-recursivelyを評価する。 つまり、triangle-recursivelyを評価すると1が返される。

手順3　numberの値を評価する。

変数numberは、+で始まるリストの2番目の要素であり、 その値は2である。

手順4　+式の評価。

+式は2つの引数、 numberの評価結果（手順3）と、triangle-recursivelyの評価結果 （手順2）を受け取る。

加算の結果は、2足す1で、数3が返される。 これは正しい値である。 2行の三角形には3個の小石がある。

引数が3の場合

引数が3の場合

引数3でtriangle-recursivelyが呼ばれた場合を考えよう。

手順1　再帰条件の評価。

最初にif式が評価される。 これは再帰条件であり偽を返すから、if式の偽の場合の動作が評価される （この例では、再帰条件が偽の場合に自身を呼び出すのであり、 真の場合には呼ばない）。

手順2　偽の場合の動作のもっとも内側の式を評価する。

偽の場合の動作のもっとも内側の式が評価され、3から2に減る。 これは次段式である。

手順3　関数triangle-recursivelyを評価する。

関数triangle-recursivelyに数2が渡される。

Emacsが、引数2でtriangle-recursivelyを評価するとどうなるかは すでに知っている。 上で述べたような動作順序のあとで、値3が返される。 ここでもそのようになる。

手順4　加算の評価。

3が加算の引数として渡され、関数呼び出しの結果の数3に加算される。

関数全体として返す値は、6になる。

これで、引数3でtriangle-recursivelyを呼ぶとどうなるかがわかった。 引数4で呼んだ場合にどうなるかも明らかであろう。

再帰呼び出しにおいて、

(triangle-recursively (1- 4))

の評価結果は、つぎの式の評価結果であり、

(triangle-recursively 3)

これは6であり、この値が3行目で4に加えられる。

関数全体として返す値は10である。

triangle-recursivelyを評価するたびに、 引数が小さくなりすぎて評価できなくなるまで、より小さな引数で自身を評価する。

11.2.3 condを用いた再帰の例

triangle-recursivelyの上の版は、 スペシャルフォームifを用いて書いた。 別のcondと呼ばれるスペシャルフォームを使っても書ける。 スペシャルフォームcondの名前は、 単語`conditional'の略である。

スペシャルフォームcondは、Emacs Lispのソースでは、 ifほど多用されないが、ここで説明するに十分なほど使われる。

cond式の雛型はつぎのとおりである。

(cond
 本体...)

本体は、一連のリストである。

より詳しく書くと、雛型はつぎのとおりである。

(cond
 ((最初の判定条件 最初の帰結動作)
  (2番目の判定条件 2番目の帰結動作)
  (3番目の判定条件 3番目の帰結動作)
  ...)

Lispインタープリタがcond式を評価するとき、 condの本体の一連の式の最初の式の最初の要素 （CAR、つまり、判定条件）を評価する。

判定条件がnilを返すと、式の残り、つまり、帰結動作は飛び越され、 つぎの式の判定条件を評価する。 判定条件がnil以外の値を返す式がみつかると、 その式の帰結動作を評価する。 帰結動作は、複数個の式でよい。 帰結動作が複数個の式の場合、それらの式は順番に評価され、 最後のものの値が返される。 式に動作がない場合には、判定条件の値が返される。

真となる判定条件がない場合には、cond式はnilを返す。

condを用いて書くと、関数triangleはつぎのようになる。

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

この例では、condは、数が0より小さいか等しい場合には0を返し、 数が1の場合には1を返し、 数が1より大きい場合には、(+ number (triangle-using-cond (1- number)))を 評価する。

11.3 ループの演習問題

• triangleに似た関数で、各行には行の番号の2乗の値があるような関数を 書いてみよ。 whileを使うこと。

• triangleに似た関数で、加算のかわりに乗算を使う関数を書いてみよ。

• これらの2つの関数を再帰的に書き直してみよ。 これらの関数をcondを使うように直してみよ。

• 段落内の各`@dfn'に対するインデックスをその段落の始めに作るような Texinfoモード用の関数を書いてみよ （Texinfoファイルでは、`@dfn'は定義に印を付ける。 詳しくは、 @xref{Indicating, , Indicating Definitions, texinfo}.)