大昔の Lisp には繰り返しの関数が用意されていませんでした。ではどうやって繰り返しを実現していたかというと、「再帰定義 (recursive definition)」を使っていたのです。再帰定義とは、関数がその中で自分自身を呼び出すことをいいます。「再帰呼び出し (recursive call)」ともいいます。
Common Lisp の場合、便利な繰り返し関数が用意されているので、単純な繰り返しは再帰定義を使わなくても簡単にプログラムできます。だからといって、再帰定義が不用になったわけではなく、重要なテクニックであることに変わりはありません。
関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないか、と思われるかもしれません。M.Hiroi が最初に再帰定義を見たときは、ヘビが自分の尻尾を食べていくような奇妙な感覚に陥って、なかなか理解できませんでした。
ところが、再帰定義は特別なことではありません。ましてや Lisp の専売特許でもないのです。Ｃ言語や Perl など近代的なプログラミング言語であれば、再帰定義を使うことができるのです。 残念なことですが Lisp 以外のプログラミング言語では、再帰定義を難しいテクニックのひとつと思い込んでしまい、初心者の方は避けて通ることが多いように思います。
再帰呼び出しは、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。とくに Lisp の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。
階乗の定義からわかるように、x の階乗を求めるには (x - 1) の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができるのです。
リスト : 再帰の例（その１）
(defun fact (x)
(if (zerop x)
1
(* x (fact (1- x)))))
最後で fact 自身を再帰呼び出ししています。それでは、このプログラムの動作を説明します。次の図を見てください。
┌───── (fact 4) => 24 ─────┐
│ X = 4 │
│ (* 4 (fact 3)) │
│ │
│┌──── (fact 3) => 6 ────┐│
││ X = 3 ││
││ (* 3 (fact 2)) ││
││ ││
││┌─── (fact 2) => 2 ───┐││
│││ X = 2 │││
│││ (* 2 (fact 1)) │││
│││ │││
│││┌── (fact 1) => 1 ──┐│││
││││ X = 1 ││││
││││ (* 1 (fact 0)) ││││
││││ ││││
││││┌─ (fact 0) => 1 ─┐││││
│││││ X = 0 │││││
│││││ 1 │││││
││││└──────────┘││││
│││└────────────┘│││
││└──────────────┘││
│└────────────────┘│
└──────────────────┘
図 : 再帰呼び出し
fact に 4 を与えて呼び出してみましょう。引数 X には 4 が代入されます。引数 X の値は (fact 4) が実行されている間だけ有効です。上図では、そのことを枠で示しています。この場合、X は 0 ではないので、else 節が実行されます。最初の枠の中を見てください。ここで X の値から 1 引いた値で自分自身を呼び出しています。
次に、2 番目の枠の中を見てください。引数 X には 3 が代入されます。関数を呼び出す場合、Lisp は引数用にメモリを割り当て、そこに実引数を書き込みます。再帰呼び出しであっても、普通の関数呼び出しには違いありません。したがって (fact 3) を実行する場合も、引数 X に対応するメモリ領域を割り当て、そこに実引数である 3 を代入します。つまり、(fact 4) と (fact 3) の呼び出しでは、引数 X に割り当てられるメモリは異なっているのです。ここが再帰呼び出しを理解するポイントのひとつです。
プログラムを見ると引数 X はひとつの領域しかないように見えますが、関数を呼び出すたびに、レキシカル変数は新しいメモリに割り当てられていくのです。したがって、(fact 4) を呼び出したときの X の値が更新されるのではありません。(fact 4) を実行しているときの X は 4 で、(fact 3) を実行しているときの X は 3 なのです。再帰呼び出しが行われるたびに、新しい X が作られると考えてください。
同様に (fact 2), (fact 1), (fact 0) と順番に呼び出していきます。(fact 0) の場合、X は 0 ですから then 節が実行されます。ここで再帰呼び出しが止まります。ここが第 2 のポイントです。
停止条件を作らなかったり、作ってもその条件を満たさないならプログラムは正常に動作しません。停止条件がなかったり条件を満たさない場合、関数呼び出しが限りなく行われるので、Lisp のシステム資源 (メモリ) を食い潰し、いつかはプログラムを実行できなくなります。
(fact 0) は 1 を返します。関数を呼び出した場合、それを呼び出した関数に必ず戻ります。この場合は (fact 0) が終了したので、(fact 1) の実行に戻るのです。(fact 1) の実行は終了していないので、引数 X の値は 1 になります。図でいえば、実行が終了したら枠が壊れていくと考えてください。いちばん内側の枠が壊れて、その前に値を代入されたレキシカル変数が顔を出すのです。
(fact 0) が 1 を返してきたので、(fact 1) を計算することができます。(* 1 1) を評価して (fact 1) は 1 を返します。同様に、順番に値を計算していき、最後に (fact 4) の値を求めることができるのです。
ところで、Common Lisp には関数の呼び出しを追跡するトレース機能が用意されています。
(trace 関数名) (untrace 関数名)
trace でトレースをオンに、untrace でトレースをオフにします。関数名に引用符 ' を付ける必要はありません。たとえば、fact をトレースすると次のようになります。
* (trace fact)
(FACT)
* (fact 4)
0: (FACT 4)
1: (FACT 3)
2: (FACT 2)
3: (FACT 1)
4: (FACT 0)
4: FACT returned 1
3: FACT returned 1
2: FACT returned 2
1: FACT returned 6
0: FACT returned 24
24
* (untrace fact)
T
プログラムをデバッグするとき、トレースはとても役に立つ機能ですが、関数の動作を調べるときにも活用することができます。
もう一つ簡単な例として累乗 xy を求める関数を作ってみましょう。Common Lisp には関数 expt があるので、名前を pow としました。累乗は x の y 乗という x を y 回掛ける計算です。ここでは x ** y と書くことにします。
(pow x y) = x ** y x ** 3 = x * x * x; x ** 4 = x * x * x * x; x ** 5 = x * x * x * x * x; 図 : 累乗の計算
今回のプログラムは引数 y を正整数とします。そうすると、x ** y は次のように定義することができます。
階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。
リスト : 累乗 (1)
(defun pow (x y)
(if (zerop y)
1
(* x (pow x (1- y)))))
再帰定義を使って x ** y を計算しています。手続き型言語では単純な繰り返しで実現できる処理ですが、純粋な関数型言語では単純な繰り返しでも再帰定義を使って実現します。Common Lisp には単純な繰り返しがあるので安心してください。
簡単な実行例を示します。
* (pow 2 8) 256 * (pow 2 16) 65536 * (pow 2 32) 4294967296
(pow x y) は Y 回の掛け算をしなくてはいけませんが、式を変形するともっと少ない回数で累乗を求めることがでます。次の式を見てください。
x ** 4 = (x ** 2) ** 2 -> 2 回
x ** 8 = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回
一般化すると
x ** y = (x ** (y / 2)) ** 2 （y は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （y は奇数）
図 : 累乗の高速化
階乗の計算では N を N - 1 の計算に置き換えていきますが、累乗の場合は Y を Y / 2 に置き換えていくことができます。Y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。これを単純にプログラムすると、次のようになります。
リスト : 累乗 (2)
(defun pow1 (x y)
(if (zerop y)
1
(let ((z (pow1 x (floor y 2))))
(if (evenp y)
(* z z)
(* x z z)))))
変数 Z の値は X ** (Y / 2) です。これは pow1 を再帰呼び出しすれば簡単に求めることができます。あとは、Y が偶数であれば、Z * Z を返し、奇数であれば X * Z * Z を返します。
簡単な実行例を示します。
* (pow1 2 16) 65536 * (pow1 2 32) 4294967296 * (pow1 2 64) 18446744073709551616
次は、再帰定義を使ってリスト操作を行ってみましょう。リスト操作と再帰定義は相性が良いのです。まずは、リストの要素を数えるプログラムを作ります。Common Lisp には length という同等以上の機能を持つ関数が用意されていますが、再帰定義を使えば簡単に作ることができます。
まず、いちばん簡単な場合を考えます。引数が空リスト nil であれば 0 を返せばいいですね。あとは、リストが空リストになるように分解していけばいいのです。つまり、リスト x の要素の個数を求めるには、リスト x に cdr を適用したリストの要素の個数がわかればいい、と考えるのです。それに 1 を足せば、要素の個数を求めることができます。これをプログラムすると、次のようになります。
リスト : リストの要素を数える
(defun my-length (x)
(if (atom x)
0
(1+ (my-length (cdr x)))))
引数がアトムなら 0 を返します。そうでなければ、引数を cdr して my-length を再帰呼び出しします。リストに cdr を繰り返し適用していくと最後は空リスト NIL になります。NIL はアトムですから、ここで再帰呼び出しが止まって 0 を返します。そうすると、1+ によって my-length の返り値に 1 を足した値を返していきます。すなわち cdr した回数だけ 1 が足されるわけです。
my-length をトレースすると次のようになります。
* (my-length '(a b c d))
0: (MY-LENGTH (A B C D))
1: (MY-LENGTH (B C D))
2: (MY-LENGTH (C D))
3: (MY-LENGTH (D))
4: (MY-LENGTH NIL)
4: MY-LENGTH returned 0
3: MY-LENGTH returned 1
2: MY-LENGTH returned 2
1: MY-LENGTH returned 3
0: MY-LENGTH returned 4
4
もう一つ簡単な例として、リスト xs の先頭から n 個の要素を取り除く関数を取り上げます。Common Lisp には関数 nthcdr n xs が用意されているので、ここでは関数 drop xs n を作ることにします。名前は Scheme から拝借しました。nthcdr と drop では引数の順番が逆になっていることに注意してください。
この関数は名前 nthcdr が示すように、XS に cdr を N 回適用すれば実現できます。これも再帰定義で簡単にプログラムすることができます。次のリストを見てください。
リスト : 先頭から n 個の要素を取り除く
(defun drop (xs n)
(if (or (null xs) (zerop n))
xs
(drop (cdr xs) (1- n))))
drop を再帰呼び出しするとき、引数 XS に cdr を適用し、引数 N を -1 します。再帰呼び出しの停止条件は XS が空リストになるか N が 0 になるときです。それでは実行してみましょう。
* (drop '(a b c d e) 3) (D E) * (drop '(a b c d e) 1) (B C D E) * (drop '(a b c d e) 5) NIL
Common Lisp にはリスト XS の N 番目の要素を返す関数 nth n xs がありますが、nthcdr を使うと次のように定義することができます。
リスト : 関数 nth の定義 (defun nth (n xs) (car (nthcdr n xs)))
* (nth 0 '(a b c d e)) A * (nth 2 '(a b c d e)) C * (nth 4 '(a b c d e)) E
Common Lisp の場合、リストの先頭要素は 0 番目になります。0 から数え始めることに注意してください。
次は関数 append を作ってみましょう。関数名は my-append とします。引数としてリスト XS と YS を渡して、それを結合したリストを返します。
処理手順ですが、簡単な場合から考えていきましょう。まず、リスト XS が空リスト NIL ならば、リスト YS を返すだけでいいですね。次に、リスト XS に要素が 1 つしかない場合を考えてみます。これは、リスト XS に car を適用して要素を取り出し、それを cons でリスト YS の先頭に追加すればいいでしょう。
それでは、リスト XS に要素が複数ある場合を考えてください。リスト XS に cdr を適用すれば空リストになりますから、この処理は再帰定義で実現することができます。つまり、リスト XS とリスト YS を結合するには、リスト XS の cdr とリスト YS を結合したリストに、リスト XS の car を cons すればいいのです。これを図に示すと次のようになります。
┌────────────────────────────┐
│(my-append '(1 2) '(3 4)) │
├────────────────────────────┤
│ ( 1 2 ) │
│ ┬ ── cdr ─┐ │
│ car ↓ │
│ │ ┌──────────────────────┐│
│ │ │(my-append '(2) '(3 4)) ││
│ │ ├──────────────────────┤│
│ │ │ ( 2 ) ││
│ │ │ ┬ ─ cdr ─┐ ││
│ │ │ car ↓ ││
│ │ │ │ ┌────────────────┐││
│ │ │ │ │(my-append NIL '(3 4)) => (3 4) │││
│ │ │ │ └────────────────┘││
│ │ │ │ │ ││
│ │ │ └→ cons ←─┘ ││
│ │ │ (2 3 4) ││
│ │ └─────┼────────────────┘│
│ └──→ cons ←─┘ │
└──────┼─────────────────────┘
↓
(1 2 3 4)
図 : my-append の動作
これをプログラムすると次のようになります。
リスト : リストの結合
(defun my-append (xs ys)
(if (null xs)
ys
(cons (car xs) (my-append (cdr xs) ys))))
引数 XS が空リストであればリスト YS をそのまま返します。そうでなければ、リスト XS に cdr を適用した値を my-append に渡して再帰呼び出しします。そして、その結果とリスト XS の car を cons で接続すればいいのです。
my-append をトレースすると次のようになります。
* (my-append '(1 2) '(3 4))
0: (MY-APPEND (1 2) (3 4))
1: (MY-APPEND (2) (3 4))
2: (MY-APPEND NIL (3 4))
2: MY-APPEND returned (3 4)
1: MY-APPEND returned (2 3 4)
0: MY-APPEND returned (1 2 3 4)
(1 2 3 4)
Common Lisp の関数 member x xs は、リスト XS の中から X と等しい要素を探します。見つけた場合、その要素以降のリストを返します。見つからない場合は NIL を返します。member は Lisp の伝統的な関数の一つです。member も再帰定義で簡単にプログラムすることができます。
リスト : リストの探索
(defun my-member (x xs)
(if (or (null xs) (eql (car xs) x))
xs
(my-member x (cdr xs))))
関数名は my-member としました。再帰呼び出しするとき、引数 XS に cdr を適用するところは今までと同じです。再帰呼び出しの停止条件は、XS が空リストか、それとも (car xs) が X と等しい場合です。等値の判定には述語 eql を使っています。これは Common Lisp の member も同じです。条件を満たしていたら引数 XS を返します。
それでは実行してみましょう。
* (my-member 'a '(a b c d e)) (A B C D E) * (my-member 'c '(a b c d e)) (C D E) * (my-member 'e '(a b c d e)) (E) * (my-member 'f '(a b c d e)) NIL
Common Lisp は NIL を偽に、それ以外を真と判定するので、member を述語として使用することができます。
Common Lisp の関数 remove x xs は、リスト XS から引数 X と等しい要素を取り除いた新しいリストを返します。この関数も再帰定義で簡単にプログラムすることができます。次のリストを見てください。
リスト : リストの削除
(defun my-remove (x xs)
(cond
((null xs) nil)
((eql (car xs) x)
(my-remove x (cdr xs)))
(t (cons (car xs)
(my-remove x (cdr xs))))))
関数名は my-remove としました。cond の最初の節で XS が空リストかチェックします。これが再帰呼び出しの停止条件になります。この場合は NIL を返します。あとは、my-remove の返り値に X とは異なる要素を cons で追加すればいいわけです。
2 番目の節で、(car xs) が X と等しいかチェックします。等値の判定には eql を使います。そうであれば、my-remove を再帰呼び出しするだけです。これで (car xs) を削除することができます。最後の節では、my-remove の返り値に (car xs) を cons で追加します。
それでは実行してみましょう。
* (my-remove 'a '(a b c a b c)) (B C B C) * (my-remove 'b '(a b c a b c)) (A C A C) * (my-remove 'c '(a b c a b c)) (A B A B) * (my-remove 'd '(a b c a b c)) (A B C A B C) * (my-remove 'a '(a a a a a)) NIL
今度は、もう少し複雑な操作を行ってみましょう。リストの要素を置き換える関数を作ってみます。Common Lisp には subst old new xs という関数が用意されていますが、再帰定義を使えば簡単に作ることができます。関数名は my-subst としました。簡単な使用例を示しましょう。
(my-subst 'a 'z '(a b a c d a)) => (Z B Z C D Z) (my-subst 'a 1 '(a b (a c) (d . a))) => (1 B (1 C) (D . 1))
最初の例は、シンボル A をシンボル Z に置き換えます。次の例では、シンボル A を 1 に置き換えます。入れ子になったリストの中もデータを置き換えることに注意してください。プログラムは次のようになります。
リスト : リストの要素を置き換える
(defun my-subst (old new tree)
(cond
((equal old tree) new)
((atom tree) tree)
(t (cons (my-subst old new (car tree))
(my-subst old new (cdr tree))))))
ポイントは、リストを car と cdr に分解して再帰呼び出しするところです。car と cdr で分解したリストは cons で合成できることを思い出してください。my-subst の評価値を cons で組み立てるわけです。これは、リストを操作する場合の常套手段ですので、ぜひ覚えておいてください。
あとは、再帰呼び出しの停止条件を定めるだけです。equal を使って old と等しいか判断し、そうであれば new を返します。そうでなければ atom を使って引数 tree がアトムか判断します。
アトムであればこれ以上分解できませんので、tree をそのまま返します。そうでなければ car とcdr を使って分解し、my-subst を再帰呼び出しするわけです。
my-subst をトレースすると次のようになります。
* (my-subst 'a 1 '((a . b) (c . a)))
0: (MY-SUBST A 1 ((A . B) (C . A)))
1: (MY-SUBST A 1 (A . B))
2: (MY-SUBST A 1 A)
2: MY-SUBST returned 1
2: (MY-SUBST A 1 B)
2: MY-SUBST returned B
1: MY-SUBST returned (1 . B)
1: (MY-SUBST A 1 ((C . A)))
2: (MY-SUBST A 1 (C . A))
3: (MY-SUBST A 1 C)
3: MY-SUBST returned C
3: (MY-SUBST A 1 A)
3: MY-SUBST returned 1
2: MY-SUBST returned (C . 1)
2: (MY-SUBST A 1 NIL)
2: MY-SUBST returned NIL
1: MY-SUBST returned ((C . 1))
0: MY-SUBST returned ((1 . B) (C . 1))
((1 . B) (C . 1))
FizzBuzz 問題は単純な繰り返しで簡単に解くことができますが、Common Lisp の繰り返しはまだ説明していないので、ここでは 1 から 100 の整数を再帰定義で生成することにします。次のリストを見てください。
リスト : FizzBuzz 問題 (1)
;; 再掲
(defun fizzbuzz (x)
(cond
((zerop (mod x 15)) 'fizzbuzz)
((zerop (mod x 3)) 'fizz)
((zerop (mod x 5)) 'buzz)
(t x)))
(defun fizzbuzz-solver (s e)
(unless (> s e)
(print (fizzbuzz s))
(fizzbuzz-solver (1+ s) e)))
fizzbuzz-solver は s 以上 e 以下の整数列を生成します。引数 s と e には 1 と 100 を渡します。s >e が再帰呼び出しの停止条件です。これを満たしていなければ、fizzbuzz を呼び出して整数値 s を変換し、それを print で出力します。そして、fizzbuzz-solver を再帰呼び出しします。このとき、引数 s の値を 1+ で一つ増やすことを忘れないでください。
これで、(fizzbuzz-solver 1 100) と呼び出せば、FizzBuzz 問題を解くことができます。それでは実際に実行してみましょう。
* (fizzbuzz-solver 1 100) 1 2 FIZZ 4 BUZZ FIZZ 7 ・・・省略・・・ 94 BUZZ FIZZ 97 98 FIZZ BUZZ NIL
FizzBuzz 問題の解をリストに格納して返すことも簡単です。次のリストを見てください。
リスト : FizzBuzz 問題 (2)
(defun fizzbuzz-list (s e)
(if (> s e)
nil
(cons (fizzbuzz s) (fizzbuzz-list (1+ s) e))))
fizzbuzz-list は再帰関数で、返り値がリストになります。再帰の停止条件は fizzbuzz-solver と同じですが、ここで空リスト NIL を返します。あとは fizzbuzz-list を再帰呼び出しして、その返り値 (リスト) の先頭に cons で (fizzbuzz s) の返り値を追加していくだけです。
これで s から e までの整数列を fizzbuzz で変換することができます。それでは実際に試してみましょう。
* (fizzbuzz-list 1 100) (1 2 FIZZ 4 BUZZ FIZZ 7 8 FIZZ BUZZ 11 FIZZ 13 14 FIZZBUZZ 16 17 FIZZ 19 BUZZ FIZZ 22 23 FIZZ BUZZ 26 FIZZ 28 29 FIZZBUZZ 31 32 FIZZ 34 BUZZ FIZZ 37 38 FIZZ BUZZ 41 FIZZ 43 44 FIZZBUZZ 46 47 FIZZ 49 BUZZ FIZZ 52 53 FIZZ BUZZ 56 FIZZ 58 59 FIZZBUZZ 61 62 FIZZ 64 BUZZ FIZZ 67 68 FIZZ BUZZ 71 FIZZ 73 74 FIZZBUZZ 76 77 FIZZ 79 BUZZ FIZZ 82 83 FIZZ BUZZ 86 FIZZ 88 89 FIZZBUZZ 91 92 FIZZ 94 BUZZ FIZZ 97 98 FIZZ BUZZ)
正しく動作していますね。
最後に、再帰定義の例題として有名なハノイの塔を取り上げます。ハノイの塔は棒に刺さっている円盤を、次に示す規則に従ってほかの棒にすべて移動させる問題です。
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、5 番目の円盤を左から中央の棒に移す場合、その上の 4 枚の円盤を右の棒に移しておけば、5 番目の円盤を動かすことができるようになります。そして、5 番目の円盤を中央に移したら、右の棒に移した 4 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。
これを素直にプログラムすると次のようになります。
リスト : ハノイの塔
(defun hanoi (n from to via)
(cond
((= n 1)
(format t "from ~A to ~A~%" from to))
(t
(hanoi (1- n) from via to)
(format t "from ~A to ~A~%" from to)
(hanoi (1- n) via to from))))
n は動かす円盤の枚数、from は移動元の棒、to は移動先の棒、via は残りの棒を示します。円盤の枚数が 1 枚の場合は簡単ですね。from にある円盤を to へ移すだけです。これが再帰の停止条件になります。format の ~A は与えられた引数を表示するための変換指定子、~% は改行するための変換指定子です。この場合、最初の ~A が from の値を、次の ~A が to の値を表示します。
円盤が複数枚ある場合、from にある円盤の n - 1 枚を via に移します。この処理は hanoi を再帰呼び出しすればいいですね。次に、残りの 1 枚を to に移します。これを format で表示します。そして、via に移した n - 1 枚の円盤を to に移します。この処理も hanoi を再帰呼び出しするだけです。これでプログラムは完成です。それでは実行してみましょう。
* (hanoi 3 'a 'b 'c)
from A to B
from A to C
from B to C
from A to B
from C to A
from C to B
from A to B
NIL
* (trace hanoi)
(HANOI)
* (hanoi 3 'a 'b 'c)
0: (HANOI 3 A B C)
1: (HANOI 2 A C B)
2: (HANOI 1 A B C)
from A to B
2: HANOI returned NIL
from A to C
2: (HANOI 1 B C A)
from B to C
2: HANOI returned NIL
1: HANOI returned NIL
from A to B
1: (HANOI 2 C B A)
2: (HANOI 1 C A B)
from C to A
2: HANOI returned NIL
from C to B
2: (HANOI 1 A B C)
from A to B
2: HANOI returned NIL
1: HANOI returned NIL
0: HANOI returned NIL
NIL
次の関数を定義してください。
公式 (1) は階乗を求める関数 fact を使えば簡単ですが、ここで s から e までの整数を乗算する関数 product s e を定義すると、関数 comb は次のようになります。
リスト : 組み合わせの数 (1)
(defun product (s e)
(if (= s e)
s
(* e (product s (1- e)))))
(defun comb1 (n r)
(/ (product (1+ (- n r)) n) (product 1 r)))
* (comb1 5 3) 10 * (comb1 10 5) 252 * (comb1 30 15) 155117520 * (comb1 50 25) 126410606437752
公式 (2) と (3) は数式をそのままプラムするだけです。
リスト : 組み合わせの数 (2)
(defun comb2 (n r)
(if (or (= n r) (zerop r))
1
(/ (* (comb2 n (1- r)) (1+ (- n r))) r)))
(defun comb3 (n r)
(if (or (= n r) (zerop r))
1
(+ (comb3 (1- n) (1- r)) (comb3 (1- n) r))))
comb3 は if の eles 節で自分自身を 2 回呼びだしていますね。これを「二重再帰」といいます。trace を使って comb3 の呼び出しを追跡すると、次のようになります。
* (trace comb3)
(COMB3)
* (comb3 4 2)
0: (COMB3 4 2)
1: (COMB3 3 1)
2: (COMB3 2 0)
2: COMB3 returned 1
2: (COMB3 2 1)
3: (COMB3 1 0)
3: COMB3 returned 1
3: (COMB3 1 1)
3: COMB3 returned 1
2: COMB3 returned 2
1: COMB3 returned 3
1: (COMB3 3 2)
2: (COMB3 2 1)
3: (COMB3 1 0)
3: COMB3 returned 1
3: (COMB3 1 1)
3: COMB3 returned 1
2: COMB3 returned 2
2: (COMB3 2 2)
2: COMB3 returned 1
1: COMB3 returned 3
0: COMB3 returned 6
6
comb3 は同じ値を何回も求めているため、効率がとても悪いのです。このため、大きな値を求めると時間がかかってしまいます。
* (time (comb3 30 15)) Evaluation took: 4.995 seconds of real time 4.984375 seconds of total run time (4.984375 user, 0.000000 system) 99.78% CPU 11,987,912,896 processor cycles 0 bytes consed 155117520
comb1, comb2 では一瞬で答えが求まりますが、comb3 では約 5 秒もかかります。組み合わせの数を求めるときは、公式 (3) を使わないほうがいいでしょう。
リスト : フィボナッチ数
(defun fibo (n)
(if (< n 2)
n
(+ (fibo (1- n)) (fibo (- n 2)))))
* (fibo 2) 1 * (fibo 3) 2 * (fibo 4) 3 * (fibo 5) 5 * (fibo 6) 8
関数 fibo も二重再帰なので、大きな値を求めると時間がかかります。
* (trace fibo)
(FIBO)
* (fibo 5)
0: (FIBO 5)
1: (FIBO 4)
2: (FIBO 3)
3: (FIBO 2)
4: (FIBO 1)
4: FIBO returned 1
4: (FIBO 0)
4: FIBO returned 0
3: FIBO returned 1
3: (FIBO 1)
3: FIBO returned 1
2: FIBO returned 2
2: (FIBO 2)
3: (FIBO 1)
3: FIBO returned 1
3: (FIBO 0)
3: FIBO returned 0
2: FIBO returned 1
1: FIBO returned 3
1: (FIBO 3)
2: (FIBO 2)
3: (FIBO 1)
3: FIBO returned 1
3: (FIBO 0)
3: FIBO returned 0
2: FIBO returned 1
2: (FIBO 1)
2: FIBO returned 1
1: FIBO returned 2
0: FIBO returned 5
5
* (untrace fibo)
T
* (time (fibo 40))
Evaluation took:
3.565 seconds of real time
3.578125 seconds of total run time (3.578125 user, 0.000000 system)
100.36% CPU
8,557,862,430 processor cycles
0 bytes consed
102334155
フィボナッチ数は簡単な方法で高速に求めることができます。関数 fibo の高速化はあとで取り上げます。
リスト : リスト XS は YS よりも長いか
(defun longerp (xs ys)
(cond ((null xs) nil)
((null ys) t)
(t (longerp (cdr xs) (cdr ys)))))
; 別解
(defun longerp1 (xs ys)
(and (consp xs)
(or (null ys)
(longerp1 (cdr xs) (cdr ys)))))
* (longerp '(a b c) '(1 2)) T * (longerp '(a b c) '(1 2 3)) NIL * (longerp '(a b c) '(1 2 3 4)) NIL
リストの先頭から順番にたどり、途中で ys が空リストになれば ys の方が長いことがわかります。length でリストの長さを求めて比較するよりも、このプログラムの方が効率的だと思います。
リスト : リストの先頭から N 個の要素を取り出す
(defun take (xs n)
(if (or (null xs) (zerop n))
nil
(cons (car xs) (take (cdr xs) (1- n)))))
* (take '(a b c d e) 3) (A B C) * (take '(a b c d e) 5) (A B C D E) * (take '(a b c d e) 0) NIL
引数 XS が空リストまたは引数 N が 0 の場合は NIL を返します。そうでなければ take を再帰呼び出しして、その返り値にリストの先頭要素 (car xs) を追加します。このとき、引数 XS に適用し、N の値を -1 することをお忘れなく。
リスト : リストの反転
(defun my-reverse (xs)
(if (null xs)
nil
(append (my-reverse (cdr xs)) (list (car xs)))))
my-reverse の考え方は簡単です。(cdr xs) を my-reverse で反転し、その結果 (リスト) の末尾に (car xs) を append で連結します。とても簡単なプログラムですが、append は第 1 引数のリストをコピーするので、効率はあまりよくありません。もちろん、簡単な方法で my-reverse を改善することができます。これもあとで取り上げます。
それでは実行してみましょう。
* (my-reverse ())
NIL
* (my-reverse '(a b c d e))
(E D C B A)
* (trace my-reverse)
(MY-REVERSE)
* (my-reverse '(a b c d e))
0: (MY-REVERSE (A B C D E))
1: (MY-REVERSE (B C D E))
2: (MY-REVERSE (C D E))
3: (MY-REVERSE (D E))
4: (MY-REVERSE (E))
5: (MY-REVERSE NIL)
5: MY-REVERSE returned NIL
4: MY-REVERSE returned (E)
3: MY-REVERSE returned (E D)
2: MY-REVERSE returned (E D C)
1: MY-REVERSE returned (E D C B)
0: MY-REVERSE returned (E D C B A)
(E D C B A)