LispのL-99 その2

前回の続きP04から

P04は「要素の数を返すnumber-of-elements関数を作る」という問題。
「むむむ...lengthじゃだめですか...」
ということで以下のようなものになりました。

(defun number-of-elements (l)
  (if (atom l)
      nil
      (cond
        ((null l) 0)
        (t (1+ (number-of-elements (cdr l))))))

----
結果
----
* (number-of-elements '())
0
* (number-of-elements '(a b c d))
4

まずリストかどうかチェックして、空リストならば0。それ以外はcdrの方を再帰的に見ていきます。1+は関数で、単に1加算した新しい値を返します。例えば要素が1つの場合、cdrはnilなので、0 + 1の値、つまり1を返します。
続いてP05は「リストを反転させるreverse-list関数を作る」という問題。
「reverseを使えば...」
以下のようになりました。

(defun reverse-list (l)
  (if (atom l)
      nil
      (if (eql (length l) 1)
          l
          (append (reverse-list (cdr l))
                  (list (car l))))))

----
結果
----
* (reverse-list '(a b c d))
(D C B A)

まずリストかどうかチェック。リストの長さが1ならば、反転してもそのままなので、そのまま返す。そうでなければ再帰処理に入っていきます。再帰は私自身も時々訳が解からなくなる代物ですが、簡単なものから始めて、図で書いてみると理解が進むように思います。例えば上記の処理の場合、以下のような形で処理が進んでいきます。

わかりにくい図で申し訳ありません。まず引数lはリストであり、長さも１ではないので、appendの部分に処理が移行しますが、そこにもreverse-list関数がありますので、その結果待ちとなります。そしてその処理は(reverse-list '(b c d))なので、またしてもappendのところで結果待ちになります。そして次は(reverse-list '(c d))となり、ここでもappendのところで(reverse-list '(d))の結果待ちになりますが、その結果は長さが１なのでDとなります。すると結果待ちだった１つ前の処理は(D C)と確定します。さらにもう1つ前の結果も確定し(D C B)となります。さらにずっと結果を待っていた最初の処理は、結果が確定したので処理を進めます。そして(D C B A)という結果になります。
私は、再帰は簡単なもの、つまり図で描ける範囲だと、なんとか理解できますが、複雑なものになると途中で分からなくなってしまうので、図を描かなくてもすらすら書けてしまう「再帰ッカー」の方々は尊敬に値します。