Re: [bep] learning lisp: recursive

[TAKAHASHI Naoto <ntakahas@m17n.org>]

n高橋です。

Reiko TAKAHASHI  (高橋玲子)writes:

> 　nと2をかけたものだと(2* n)って書いたりもできるんですか？

普通は (* 2 n) と正直に書きますが、自分で関数を定義すればそういう書き
方もできます。

(defun 2* (n) (* 2 n))

アルファベットが入っていませんが、2* というシンボルが関数名です。

プログラムを書いていると 1+ と 1- は非常によく使うので、この二つは
Emacs Lisp が最初から用意してくれています。

> } (defun fact (n)
> }   (if (= n 1)
> }       1
> }     (* n (fact (- n 1)))))

> (defun fact (n)

> 関数名は fact で、そこで使う引数はn。

>   (if (= n 1)

> nが１だったら

>       1

> 1（って……なんでしょう……？）。
> 1っていう値を返してっていうことですか？

そうです。

>     (* n (fact (- n 1)))))

> そうでなければ、n と (fact (- n 1))をかける。

そのとおり。

> fact (- n 1) は……？
> factって、その寸前というか、すぐ外(?)で定義してるんですよね？　こんなこと
> ができるなんて不思議というか、やっぱりわからないかも。

このように、自分自身を使って関数を定義することを再帰的定義と言います。
また関数の中から自分自身を呼び出すことを、再帰的呼び出し (recursive
call) といいます。

> n が 1だったら、n=1なので 1？

> n が 2だったら……。
> (* 2 (fact (- 2 1))) ==> (* 2 fact(1))
> で、fact(1) は……あちゃあ、わかんない〜(^_^;)。

書き方の問題ですが、fact(1) ではなくて (fact 1) ですね。

> ()の中が1だから、n=1(???)だから、1……？

そうです。すぐ上でやったように、(fact 1) は (= n 1) を満たしますから、
これを評価した結果(つまり答)は1になります。で、(fact 2) は
(* 2 (fact 1)) ですから、(* 2 1) つまり2です。

前にも書きましたが、普通関数はその引数を評価してから自分を適用します。
ですからここでの関数 * は 2 を評価した結果と (fact 1) を評価した結果を
かけ合わせ、それを自分の結果とします。2は数値ですから2を評価した結果は
2そのものです。また (fact 1) は関数でそれを評価した結果は上でやったよ
うに1になります。最後に2と1をかけて2が結果となります。

> n が3 だったら……？
> (* 3 (fact (- 3 1))) ==> (* 3 fact(2))
> で、fact(2) は……
> ()の中が2だから、n=2……？　だと、あちゃあ、またわかんない(^_^;)。

すぐ上でやったように、(fact 2) は2になります。で、(fact 3) は
(* 3 (fact 2)) ですから (* 3 2) つまり6です。

種あかしをすると、fact は factorial の略です。日本語だと階乗です。聞い
たことがあると思います。数学だとnの階乗は n! と書き、

 n! = n * (n-1) * (n-2) * ... 2 * 1

です。これを書き直すと

nが1なら n! = 1  
そうでなければ n! = n * (n-1)!

となります。上の (defun fact ... はこれをそのまま Lisp に翻訳したものです。

-- 
TAKAHASHI Naoto
ntakahas@...
http://www.m17n.org/ntakahas/