この章では再帰の基本から，末尾再帰への書き換え方について解説している．またエディタにプログラムを書いてLispインタプリタに読み込む方法も説明している．
末尾再帰とは
再帰的に定義された関数の末尾で，自分自身を呼び出した戻り値をそのままリターンする関数定義．
末尾再帰の例（ユークリッドの互除法）
(defun gcd2 (m n)
(if (= (mod m n) 0) n
(gcd2 n (mod m n))))最後の行で自分自身`gcd2`への呼び出しで終わっている．すなわち，自分自身への呼び出しの戻り値をそのままリターンしている．
末尾再帰ではない例（\\(m^n\\)の計算）
(defun expt2 (m n)
(if (= n 0) 1
(* m (expt2 m (- n 1)))))最後の行で自分自身`expt2`を呼び出した戻り値をさらに`m`と掛け合わせている．
末尾再帰の効能
上の`expt2`では自分自身の呼び出しから戻った後，`m`と戻り値を掛け合わせるという処理が残っているため，呼び出し側は`m`の値を保持しておかなければならない．つまりスタックに現在の関数の状態をプッシュしてから自分自身をコールし，コールから戻ったらスタックから情報をポップして処理をする．再帰が深くなればスタックオーバーフローが発生するし処理速度も落ちる．
一方，末尾再帰の場合，自分自身の再帰的呼び出し後に処理が残っていないので，スタックに保持しておく値がない．従ってLispコンパイラは単なるループ処理のコードを生成する．
末尾再帰への書き換え方
末尾再帰は本質的にループと同じ．ループではループを１回繰り返すたび「状態」を変え，その中で処理を完結する．従って，ループ１回分の処理に必要な全状態変数を再帰呼び出しの引数に渡せば良い．呼び出しの際には適切にループ変数を更新し，境界条件で一気に状態変数を用いて処理すれば良い．
末尾再帰への書き換え例１---階乗計算
まずはテキストで説明されている階乗計算（\\(n!\\)）の書き換え例から．
通常の再帰
(defun factorial (n)
(if (= n 0) 1
(* n (factorial (- n 1)))))末尾再帰への書き換え手順
1．通常の再帰定義のようにループしながら\\(n\\)から順にデクリメントして掛け合わせていくとすると，C言語のループでは以下のように書けるだろう．
int result = 1;
for (int i=0; i<n; i++) {
result = result * (n-i)
}つまりループ１回の処理で必要な変数は，n，i，`result`の３つである．
2．終端条件は`i`が`n-1`に等しい時，result * (n-i)`を返す．`i`に`n-1`を代入すると`result．
3．初期条件は，n = n，i = 0，result = 1．
以上をまとめると次のようなコードになる．
(defun my-fact (n i result)
(if (= i (- n 1)) result
(my-fact n (+ i 1) (* result (- n i)))))
(defun factorial (n)
(my-fact n 0 1))これで，`(factorial 5)`で120を返す．
4．テキストの変換例の解説．`i=1`を初期条件として採用して1から順に`n`までインクリメントして掛け合わせている．従ってCのループは以下のようになる．
int result = 1;
for (int i=1; i <= n; i++) {
result = result * i
}従って`i > n`の時，ループから抜けて`result`を返すと答えを得るので，Lispコードは以下のようになる．
(defun text-fact (n i result)
(if (> i n) result
(text-fact n (+ i 1) (* result i))))
(defun factorial2 (n)
(text-fact n 1 1))やはりテキストのコードの方がスマートだ．
末尾再帰への書き換え例２---組み合わせ計算
<div> \[ {}_nC_k = \frac{n!}{k!(n-k)!} = {}_{n-1}C_{k-1} + {}_{n-1}C_k \] </div>
上の2項係数を実装すると以下のように２重再帰となる．
(defun C (n k)
(if (= k 0) 1
(if (= n k) 1
(+ (C (- n 1) (- k 1))
(C (- n 1) k)))))これを末尾再帰に書き換えようとしたがうまくいかなかった．ループは再帰に書き換えられるが，再帰は必ずしもループに書き換えられないので，これがその例なのかもしれない．
代わりに階乗で定義された2項係数を末尾再帰に書き換える．
<div>\[ \begin{align} {}_nC_k &= \frac{n!}{k!(n-k)!} = \frac{n}{k} \frac{(n-1)!}{(k-1)!(n-k)!} \\ &= \frac{n}{k} \cdot \frac{(n-1)!}{(k-1)!n-1)-(k-1!} \\ &= \frac{n}{k} \cdot {}_{n-1}C_{k-1} \end{align} \] </div>
まず通常の再帰で書くと以下のようになる．今回は`if`を入れ子にせず`cond`を使ってみた．
(defun C (n k)
(cond ((or (= k 0) (= n k)) 1)
(t (* (/ n k) (C (- n 1) (- k 1))))))これを末尾再帰にするには，計算結果を格納する`res`と`n`，`k`の３変数が必要だ．
(defun tail-C (n k res)
(cond ((or (= k 0) (= n k)) res)
(t (tail-C (- n 1) (- k 1) (* (/ n k) res)))))
(defun C (n k)
(tail-C n k 1))プログラムファイルのロードの仕方
(load "ファイル名")．ファイルの拡張子は`l`，lsp，`lisp`がよく使われる．
第５話に出てきた組込み関数一覧
-
mod---`(mod m n)`で\\(m\\div n\\)の余りを返す関数． -
gcd---引数の最大公約数を返す関数． -
load---Lispプログラムの入ったファイルを読み込む．