関数 format はＣ言語の標準ライブラリ関数 fprintf や sprintf に相当する関数です。いわゆる書式文字列を与えて、それに従ってデータ (S 式) を整形して出力します。関数 print のように単純に S 式を出力するのではなく、表示に関していろいろな指定を行うことができますが、その分使い方が少しだけ複雑になります。
format 出力ストリーム 書式文字列 Ｓ式 ...
format の第 1 引数は出力ストリームを指定します。ストリームに T が指定された場合は標準出力へ出力されます。NIL が指定された場合は、ストリームに出力せずに変換結果を文字列にして返します。
第 2 引数は書式文字列で、出力に関する様々な指定を行います。これには文字列型データを使います。format は文字列をそのまま出力するのですが、文字列の途中にチルダ ~ が表れると、その後ろの文字を変換指示子として理解し、引数の S 式をその指示に従って表示します。
簡単な例を示しましょう。
* (format t "１０進数表示 ~d" 256) １０進数表示 256 NIL * (format t "１６進数表示 ~x" 256) １６進数表示 100 NIL * (format t "８進数表示 ~o" 256) ８進数表示 400 NIL
NIL は format の返り値です。チルダの前までは、そのまま文字を表示します。チルダ ~ の次の文字 d, x, o が変換指示子です。これらの指示子は整数値を表示する働きをします。例が示すように、d は 10 進数、x は 16 進数、o は 8 進数で表示します。変換指示子は英大文字で記述しても大丈夫です。
書式文字列の中には、変換指示子をいくつ書いてもかまいません。
* (format t "~d ~x ~o" 256 256 256) 256 100 400 NIL
変換指示子の個数と引数として与える S 式の数が合わないとエラーになるので注意してください。また、~% は改行を表し、チルダを出力したい場合は ~~ と続けて書きます。それから、チルダ ~ と変換指示子の間に前置パラメータやコロン ( : ) 修飾子、アットマーク ( @ ) 修飾子を指定することができます。
簡単な例を示しましょう。
* (format t "[~d]" 10) [10] NIL * (format t "[~4d]" 10) [ 10] NIL * (format t "[~4d]" 10000) [10000] NIL
整数値を表示する変換指示子は、前置パラメータでデータを表示するフィールド幅を指定することができます。最初の例がフィールド幅を指定しない場合で、次の例がフィールド幅を 4 に指定した場合です。10 ではフィールド幅に満たないので、右詰めに出力されていますね。もし、フィールド幅に収まらない場合は、最後の例のように指定を無視して数値を出力します。
前置パラメータを複数指定する場合はカンマ ( , ) で区切ります。前置パラメータの意味は、変換指示子によって異なるので注意してください。簡単な例を示しましょう。
* (format t "[~4,'0d]" 10) [0010] NIL * (format t "[~4,'ad]" 10) [aa10] NIL
整数値を表示する変換指示子の場合、第 1 番目の前置パラメータでフィールド幅を指定します。第 2 番目の前置パラメータに 'a を指定すると、左側の空いたフィールドに文字 a を詰め込みます。クオート ( ' ) は前置パラメータを文字として指定するときに用いられます。最初の例では文字 0 を詰め込み、次の例では文字 a を詰め込みます。
前置パラメータに文字 v を指定すると、引数の値が前置パラメータとして用いられます。簡単な例を示します。
* (dotimes (x 4) (format t "~v,'0d~%" (+ 4 x) 10)) 0010 00010 000010 0000010 NIL * (dotimes (x 4) (format t "~v,vd~%" (+ 4 x) (elt "abcd" x) 10)) aa10 bbb10 cccc10 ddddd10 NIL
最初の例では、フィールド幅の指定に引数の値 (+ x 4) が用いられます。そして、D 変換指示子により引数 10 が表示されます。次の例では、詰め込む文字の指定に引数の値 (elt "abcd" x) が用いられます。この場合、クオートを指定する必要はありません。ここで 'v と指定すると、詰め込む文字が v になってしまいます。
整数値を表示する変換指示子の場合、@ 修飾子を指定すると符号 (+/-) が必ず表示されます。: 修飾子を指定すると、3 桁ごとにカンマ ( , ) が表示されます。簡単な例を示します。
* (format t "~@d" 10) +10 NIL * (format t "~:d" 100000000) 100,000,000 NIL * (format t "~,,' :d" 100000000) 100 000 000 NIL * (format t "~,,,4:d" 100000000) 1,0000,0000 NIL
: 修飾子を使う場合、第 3 番目の前置パラメータで表示する区切り文字を指定することができます。また、区切る桁数は第 4 番目の前置パラメータで指定することができます。@ 修飾子と : 修飾子は、変換指示子によって意味が異なります。ご注意くださいませ。
このほかに、2 進数を表示する B 変換指示子、前置パラメータで指定された基数で表示する R 変換指示子があります。
* (format t "~b" #x10000) 10000000000000000 NIL * (format t "~8r" #x10000) 200000 NIL
浮動小数点数を表示するには変換指示子 E, F, G を使います。
F 変換指示子は引数を [-]mmm.nnnn の形式に変換します。E 変換指示子は [-]m.nnnnE[+/-]xx の形式に変換します。G 変換子は引数を ~F または ~E のどちらかの形式に変換します。
簡単な例を示しましょう。
* (let ((n (* pi 1000))) (format t "~f ~e ~g" n n n)) 3141.592653589793 3.1415926535897926d+3 3141.592653589793 NIL * (let ((n pi)) (format t "~f ~e ~g" n n n)) 3.141592653589793 3.141592653589793d+0 3.141592653589793 NIL * (let ((n (/ pi 1000))) (format t "~f ~e ~g" n n n)) 0.0031415926535897933 3.141592653589793d-3 3.1415926535897930000d-3 NIL
F 変換指示子の前置パラメータの形式は ~w,d,k,overflowchar,padcharF です。
@ 修飾子を使うと、先頭に + 符号を付けることができます。簡単な例を示しましょう。
* (format t "[~10,4f]" pi) [ 3.1416] NIL * (format t "[~10,4@f]" pi) [ +3.1416] NIL * (format t "[~10,4,,,'0f]" pi) [00003.1416] NIL * (format t "[~10,8,,'*,'0f]" pi) [3.14159265] NIL * (format t "[~10,9,,'*,'0f]" pi) [**********] NIL
最後の例で、表示は 11 桁になるのでフィールド幅をオーバーします。この場合、フィールドに表示されるのが overflowchar で指定した文字 * になります。overflowchar が無い場合はフィールド幅を無視して表示されます。
E 変換指示子の前置パラメータの形式は ~w,d,e,k,overflowchar,padchar,exponentcharE です。
@ 修飾子を使うと、先頭に + 符号を付けることができます。簡単な例を示しましょう。
* (format t "[~15,5e]" pi) [ 3.14159d+0] NIL * (format t "[~15,5@e]" pi) [ +3.14159d+0] NIL * (format t "[~15,5,3e]" pi) [ 3.14159d+000] NIL * (format t "[~15,5,3,,'*,'0e]" pi) [0003.14159d+000] NIL * (format t "[~15,8,3,,'*,'0e]" pi) [3.14159265d+000] NIL * (format t "[~15,9,3,,'*,'0e]" pi) [***************] NIL
G 変換指示子はちょっと複雑なので、ここでは取り上げません。参考文献『COMMON LISP 第 2 版』や CLHS をお読みくださいませ。
文字を出力するには C 変換指示子を使います。これは関数 write-char と同じ動作をします。
* (format t "~c" #\a) a NIL * (format t "~c" #\HIRAGANA_LETTER_A) あ NIL
@ 修飾子を付けると、print, prin1 と同じ形式 (#\ 構文の形) で出力されます。
* (format t "~@c" #\a) #\a NIL * (format t "~@c" #\HIRAGANA_LETTER_A) #\HIRAGANA_LETTER_A NIL
: 修飾子を付けた場合、文字が画面に表示できない制御コードであれば、制御コードを表す名前を出力します。
* (format t "~:c" #\a) a NIL * (format t "~:c" #\Newline) Newline NIL
S 式を表示する場合は A または S 変換指示子を使います。次の例を見てください。
* (format t "~a" "hello, world") hello, world NIL * (format t "~s" "hello, world") "hello, world" NIL
A と S 変換指示子は、任意の S 式を出力できます。A は princ と同じ形式で、S は prin1 と同じ形式で出力します。
A, S 変換指示子の場合でも、第 1 番目の前置パラメータでフィールド幅を指定することができます。
* (format t "[~20a]" "hello, world") [ hello, world] NIL * (format t "[~20@a]" "hello, world") [hello, world ] NIL * (format t "[~20,,,'*a]" "hello, world") [********hello, world] NIL * (format t "~s" nil) NIL NIL * (format t "~:s" nil) () NIL
A, S 変換指示子の場合、@ 修飾子を指定するとデータは左詰めに出力されます。詰め込む文字は第 4 番目の前置パラメータで指定します。: 修飾子を指定すると、NIL の代わりに () と表示されます。
Common Lisp の format は、大文字小文字変換、条件付き実行、繰り返しなど、Ｃ言語の fprintf 以上の機能を持っています。これらの機能は M.Hiroi も使ったことがないので、皆さんといっしょに勉強しましょう。
英大文字小文字変換を行います。間に挟まれた書式文字列が処理され、その結果の文字列が変換されます。
簡単な使用例を示しましょう。
* (format t "~(~a~)" "FOO BAR") foo bar NIL * (format t "~:@(~a~)" "foo bar") FOO BAR NIL * (format t "~:(~a~)" "foo bar") Foo Bar NIL * (format t "~@(~a~)" "foo BAR") Foo bar NIL
~[ と ~] の間に定義された書式文字列をひとつ選択して実行します。書式文字列は ~; で区切られています。とくに、最後の ~; が ~:; の場合、その書式文字列はどれも選択されなかった場合に選ばれます。つまり else 節に相当します。書式文字列の選択は、最初の引数で決定されます。引数の値が 0 であれば str0 が選択され、整数値 n であれば n 番目の strn が選択されます。範囲外であれば default が選択されます。
簡単な使用例を示しましょう。
* (format t "~[foo~a~;bar~a~:;baz~a~]" 0 100) foo100 NIL * (format t "~[foo~a~;bar~a~:;baz~a~]" 1 100) bar100 NIL * (format t "~[foo~a~;bar~a~:;baz~a~]" 10 100) baz100 NIL
最初の引数が 0 であれば foo~a が選択され、その結果は foo100 となります。最初の引数は選択のために処理されるので、foo~a には次の引数 100 が与えられることに注意してください。最初の引数が 1 であれば bar100 になり、0, 1 以外の値であれば baz100 となります。
~:[false~;true~] は、引数が NIL であれば false を選択し、そうでなければ true を選択します。~@[true~] は、引数が NIL でなければ true を選択します。このとき、引数はテストされるだけで実際には処理されません。したがって、この引数を書式文字列の中で使うことができます。ただし、NIL の場合は処理されてしまいます。
簡単な使用例を示しましょう。
* (format t "~:[foo~a~;bar~a~]" t 100) bar100 NIL * (format t "~:[foo~a~;bar~a~]" nil 100) foo100 NIL * (format nil "~@[foo~a~] ~a" 100 200) "foo100 200" * (format nil "~@[foo~a~] ~a" nil 200) " 200"
最後の例では、引数が NIL なので書式文字列 foo~a は選択されませんが、その引数は処理されてしまいます。したがって、最後の ~a には引数 200 が与えられるため、" 200" という結果になります。
~ と [ の間に整数値が指定されると、その値に対応する書式文字列が選択されます。
* (format t "~1[foo~a~;bar~a~:;baz~a~]" 100) bar100 NIL
この場合、最初の引数は処理されないので、bar~a の変換指示子へ与えられることに注意してください。また、format の書式文字列では、~ と変換指示子の間に # を用いることができます。この場合、# はまだ処理されていない引数の個数を表します。# と ~[ を組み合わせることで、引数の個数により出力を変更することができます。次の例を見てください。
* (format t "~#[none~;bar~a~;bar~a_~a~:;bar_many~]" 10) bar10 NIL * (format t "~#[none~;bar~a~;bar~a_~a~:;bar_many~]" 10 100) bar10_100 NIL * (format t "~#[none~;bar~a~;bar~a_~a~:;bar_many~]" 10 100 1000) bar_many NIL
引数がひとつの場合は bar~a が選択されるので bar10 が出力されます。引数が 2 つの場合は bar~a_~a が選択され、出力は bar10_100 となります。とても便利な機能ですね。
書式文字列 str を繰り返し適用します。引数はリストでなければいけません。簡単な使用例を示しましょう。
* (format nil "~{ ~a,~}" '(a b c d))
" A, B, C, D,"
* (format nil "~{ <~a, ~a> ~}" '(a 1 b 2 c 3))
" <A, 1> <B, 2> <C, 3> "
* (format nil "~2{ <~a, ~a> ~}" '(a 1 b 2 c 3))
" <A, 1> <B, 2> "
最後の例のように、~ と { の間に繰り返しの回数を指定することができます。<~a, ~a> のように、複数の引数が必要な場合は ~:{ を使うと便利です。
* (format nil "~:{ <~a, ~a> ~}" '((a 1) (b 2) (c 3)))
" <A, 1> <B, 2> <C, 3> "
~@{ は引数にリストを用いるのではなく、残りの引数をすべて繰り返しに適用します。
* (format nil "~@{ ~a,~}" 1 2 3 4 5)
" 1, 2, 3, 4, 5,"
* (format nil "~4@{ ~a,~} ~4D" 1 2 3 4 5)
" 1, 2, 3, 4, 5"
最後の例のように、途中で繰り返しが終了して引数が残っている場合は、その後ろの変換指示子に残りの引数が与えられます。
~:@{str~} は、~@{str~} のように残りの引数が用いられますが、その引数は ~:{str~} のようにリストでなければいけません。簡単な使用例を示します。
* (format nil "~:@{ <~a, ~a> ~}" '(a 1) '(b 2) '(c 3))
" <A, 1> <B, 2> <C, 3> "
~* は次の引数を無視します。~n* のように整数値 n が指定された場合は、n 個の引数を無視します。~:* は処理した引数を元に戻します。つまり、直前に処理した引数が再び処理されます。~n:* は n 個の引数が元に戻されます。次の例を見てください。
* (format t "~a ~a ~:* ~a" 1 2 3) 1 2 2 NIL * (format t "~a ~a ~2:* ~a" 1 2 3) 1 2 1 NIL
2 つの変換指示子で引数 1, 2 は処理されますが、~:* によりひとつ戻されます。したがって、次の ~a には 2 が与えられます。~2:* では 2 つ戻されるので、~a に与えられる引数は 1 となります。
このほかにも、format にはたくさんの機能があります。詳細は「参考文献『COMMON LISP 第 2 版』や CLHS をお読みください。
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶこともあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*1] といいます。なかには Scheme [*2] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
Common Lisp の場合、末尾再帰最適化は仕様に含まれてないので、最適化の実装は処理系に依存します。もちろん、SBCL は末尾再帰最適化をサポートしています。
たとえば、階乗を計算するプログラムを思い出してください。
リスト : 階乗の計算
(defun fact (x)
(if (zerop x)
1
(* x (fact (1- x)))))
関数 fact は最後に引数 X と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると、次のようになります。
リスト : 階乗の計算 (末尾再帰)
(defun fact (n &optional (a 1))
(if (zerop n)
a
(fact (1- n) (* n a))))
最後の再帰呼び出しで、fact の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議な感じがしますね。まあ、そこが再帰呼び出しの面白いところです。このプログラムでは変数 A の使い方がポイントです。
たとえば (fact 4) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算しています。このとき、計算の途中経過を変数 A に記憶しているのです。fact の呼び出しをトレースすると、次のようになります。
* (trace fact)
(FACT)
* (fact 4)
0: (FACT 4)
1: (FACT 3 4)
2: (FACT 2 12)
3: (FACT 1 24)
4: (FACT 0 24)
4: FACT returned 24
3: FACT returned 24
2: FACT returned 24
1: FACT returned 24
0: FACT returned 24
24
変数 A には計算途中の値が格納されていることがわかりますね。このような変数を「累算変数」とか「累算器」といいます。また、拙作のページ「ラムダリストキーワード」の例題で関数 my-reverse を作りましたが、このプログラムも末尾再帰になっていて、オプションパラメータ ZS が累算変数になります。
もう一つ、わざと再帰定義を使った例を示しましょう。整数 1 から n までの総和を求める関数を作ります。次のリストを見てください。
リスト : 1 から n までの総和を求める
;;; 再帰
(defun sum (n)
(if (zerop n)
0
(+ n (sum (1- n)))))
;;; 末尾再帰
(defun sum-iter (n &optional (a 0))
(if (zerop n)
a
(sum-iter (1- n) (+ a n))))
関数 sum は再帰呼び出しの返り値に引数 N を足し算しているので「末尾再帰」ではありません。関数 sum-iter は再帰呼び出しの返り値をそのまま返しているので「末尾再帰」になっています。これを実行すると次のようになります。
* (sum 10000) 50005000 * (sum 100000) => エラー "Control stack exhausted (no more space for function call frames)." * (sum-iter 10000) 50005000 * (sum-iter 100000) 5000050000 * (sum-iter 1000000) 500000500000
sum は大きな値を計算するとスタックがオーバーフローしますが、sum-iter は大きな値でもスタックオーバーフローすることなく計算することができます。末尾再帰最適化が機能していることがわかります。
Lisp 以外の関数型言語では、繰り返しの構文が用意されていないプログラミング言語があります。また、論理型言語の Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
今度は累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。例題としてフィボナッチ数を取り上げます。フィボナッチ数は拙作のページ「再帰定義」と「配列」の問題として出題しています。フィボナッチ数の定義と二重再帰のプログラムを再掲します。
リスト : フィボナッチ数 (二重再帰版)
(defun fibo (n)
(if (< n 2)
n
(+ (fibo (1- n)) (fibo (- n 2)))))
このプログラムは二重再帰になっているので、とても時間がかかります。拙作のページ「配列」では、ベクタを使った高速化 (表計算法) を説明しましたが、二重再帰を末尾再帰に変換する方法でもプログラムを高速に実行することができます。プログラムは次のようになります。
リスト : フィボナッチ関数 (末尾再帰版)
(defun fibo (n &optional (a 0) (b 1))
(if (< n 1)
a
(fibo (1- n) b (+ a b))))
累算変数 A と B の使い方がポイントです。現在のフィボナッチ数を変数 A に、ひとつ先の値を変数 B に格納しておきます。あとは A と B を足し算して、新しいフィボナッチ数を計算すればいいわけです。fibo の呼び出しをトレースすると、次のようになります。
* (trace fibo)
(FIBO)
* (fibo 5)
0: (FIBO 5)
1: (FIBO 4 1 1)
2: (FIBO 3 1 2)
3: (FIBO 2 2 3)
4: (FIBO 1 3 5)
5: (FIBO 0 5 8)
5: FIBO returned 5
4: FIBO returned 5
3: FIBO returned 5
2: FIBO returned 5
1: FIBO returned 5
0: FIBO returned 5
5
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行できるでしょう。
「相互再帰 (mutual recursion)」とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。簡単な例を示しましょう。次のリストを見てください。
リスト : 相互再帰
(defun foo (n)
(if (zerop n)
t
(bar (1- n))))
(defun bar (n)
(if (zerop n)
nil
(foo (1- n))))
このプログラムは foo と bar が相互再帰しています。foo と bar が何をしているのか、実際に動かしてみましょう。
* (foo 10) T * (foo 11) NIL * (bar 12) NIL * (bar 13) T
結果を見ればおわかりのように、foo は n が偶数のときに真を返し、bar は n が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。
ところで、このプログラムは末尾でお互いを呼び出していますね。SBCL はこのような「相互再帰」にも最適化が適用されます。
* (foo 1000000) T * (foo 10000000) T * (foo 100000000) T
foo に大きな値を与えてもスタックオーバーフローはしません。ちなみに、CLISP では (foo 4000) でスタックオーバーフローします。CLISP では何か最適化の指定が必要なのか、それとも相互再帰の最適化は行われないのかもしれません。
今回の例題のように小さなプログラムであれば、末尾再帰を手作業で繰り返しに変換するのは簡単です。ここでは単純な loop を使って繰り返しに変換してみましょう。
リスト : loop を使った繰り返し
(defun fact (n &aux (a 1))
(loop
(if (zerop n) (return a))
(setq a (* a n))
(decf n)))
(defun sum (n &aux (a 0))
(loop
(if (zerop n) (return a))
(incf a n)
(decf n)))
(defun fibo (n &aux (a 0) (b 1))
(loop
(if (zerop n) (return a))
(psetq a b
b (+ a b))
(decf n)))
&optional 引数を &aux 引数に変更し、関数本体を loop で囲みます。再帰呼び出しの停止条件がループの脱出条件になり、あとは引数の値を処理に合わせて書き換えていくだけです。とても簡単ですね。
psetq は代入を並行に行うマクロです。
psetq symbol1 value1 symbol2 value2 ...
psetq はシンボル symbol1 に value1 を評価した結果を代入し、symbol2 に value2 を評価した結果を代入する、というように値を順番に代入します。このとき、psetq は setq と違って、値となる S 式 value1, value2, ... をすべて評価してから、その結果を変数に代入します。
簡単な例を示します。
* (setq x 100 y 200) 200 * x 100 * y 200 * (psetq x y y x) NIL * x 200 * y 100
psetq で x に y の値 200 を代入し、そのあとで x の値を y に代入しています。このとき x の値は 200 ではなく、代入される前の値 100 のままなのです。したがって、y に代入される値は 100 になります。psetq を使うと簡単に変数の値を交換することができます。
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もありえます。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです。
末尾再帰についてもう少し詳しく説明しましょう。末尾再帰の「末尾」とは、関数の最後で行われる処理のことです。とくに末尾で関数を呼び出すことを「末尾呼び出し (tail call)」といいます。関数を呼び出す場合、返ってきたあとに行う処理のため、必要な情報を保存しておかなければいけません。ところが、末尾呼び出しはそのあとに実行する処理がありません。呼び出したあと元に戻ってくる必要さえないのです。
このため、末尾呼び出しはわざわざ関数を呼び出す必要はなく、アセンブリ言語のような低水準のレベルではジャンプ命令に変換することができます。これを「末尾呼び出し最適化 (tail call optimization)」とか「末尾最適化」といいます。とくに末尾再帰は末尾で自分自身を呼び出しているので、関数の中で繰り返しに変換することができます。
また、相互再帰やもっと複雑な再帰呼び出しの場合でも、末尾最適化を適用することで、繰り返しに変換できる場合もあります。このように、再帰プログラムを繰り返しに変換してから実行することを「末尾再帰最適化 (tail recursion optimization)」といいます。厳密にいうと末尾最適化なのですが、一般的には末尾再帰最適化と呼ばれることが多いようです。最近では、Ｃ言語 (gcc や clang など) でも末尾最適化が可能になっています。
Common Lisp はコンパイルされたコードを逆アセンブルする関数 disassemble があるので、末尾最適化の結果を確かめることができます。簡単な例を示しましょう。
* (defun foo () (foo) nil)
FOO
* (disassemble 'foo)
; disassembly for FOO
; Size: 46 bytes. Origin: #x1001BA806C
; 6C: 498B4C2458 MOV RCX, [R12+88] ; no-arg-parsing entry point
; thread.binding-stack-pointer
; 71: 48894DF8 MOV [RBP-8], RCX
; 75: 4883EC10 SUB RSP, 16
; 79: 31C9 XOR ECX, ECX
; 7B: 48892C24 MOV [RSP], RBP
; 7F: 488BEC MOV RBP, RSP
; 82: B818104C20 MOV EAX, #x204C1018 ; #<FDEFN FOO>
; 87: FFD0 CALL RAX
; 89: 480F42E3 CMOVB RSP, RBX
; 8D: BA17001020 MOV EDX, #x20100017 ; NIL
; 92: 488BE5 MOV RSP, RBP
; 95: F8 CLC
; 96: 5D POP RBP
; 97: C3 RET
; 98: CC0F BREAK 15 ; Invalid argument count trap
NIL
関数 foo は foo を呼び出したあと NIL を返しているので「末尾再帰」ではありません。インテルのアセンブリ言語では、関数呼び出しの命令が CALL で、呼び出し元に戻る命令が RET です。CALL で foo を呼び出すたびにスタックを消費するので、実際に実行するとスタックオーバーフローが発生します。
次は末尾再帰の例を見てみましょう。
* (defun foo-tail () (foo-tail))
FOO-TAIL
* (disassemble 'foo-tail)
; disassembly for FOO-TAIL
; Size: 23 bytes. Origin: #x1001BA810C
; 0C: 498B4C2458 MOV RCX, [R12+88] ; no-arg-parsing entry point
; thread.binding-stack-pointer
; 11: 48894DF8 MOV [RBP-8], RCX
; 15: 31C9 XOR ECX, ECX
; 17: FF7508 PUSH QWORD PTR [RBP+8]
; 1A: B838104C20 MOV EAX, #x204C1038 ; #<FDEFN FOO-TAIL>
; 1F: FFE0 JMP RAX
; 21: CC0F BREAK 15 ; Invalid argument count trap
NIL
関数 foo-tail は末尾で自分自身を呼び出しています。末尾最適化が適用されれば、この関数は「無限ループ」になります。実際に実行することはやめてくださいね。foo-tail は末尾に CALL と RET がなく、そのかわりに無条件ジャンプ命令 JMP で自分自身にジャンプしています。末尾再帰が最適化されて無限ループになっていることがわかります。
もうひとつ、相互再帰の例を見てみましょう。
* (defun bar () (baz))
BAR
* (defun baz () (bar))
BAZ
* (disassemble 'bar)
; disassembly for BAR
; Size: 23 bytes. Origin: #x1001BA00FC
; 0FC: 498B4C2458 MOV RCX, [R12+88] ; no-arg-parsing entry point
; thread.binding-stack-pointer
; 101: 48894DF8 MOV [RBP-8], RCX
; 105: 31C9 XOR ECX, ECX
; 107: FF7508 PUSH QWORD PTR [RBP+8]
; 10A: B838104C20 MOV EAX, #x204C1038 ; #<FDEFN BAZ>
; 10F: FFE0 JMP RAX
; 111: CC0F BREAK 15 ; Invalid argument count trap
NIL
* (disassemble 'baz)
; disassembly for BAZ
; Size: 23 bytes. Origin: #x1001BA018C
; 8C: 498B4C2458 MOV RCX, [R12+88] ; no-arg-parsing entry point
; thread.binding-stack-pointer
; 91: 48894DF8 MOV [RBP-8], RCX
; 95: 31C9 XOR ECX, ECX
; 97: FF7508 PUSH QWORD PTR [RBP+8]
; 9A: B858104C20 MOV EAX, #x204C1058 ; #<FDEFN BAR>
; 9F: FFE0 JMP RAX
; A1: CC0F BREAK 15 ; Invalid argument count trap
NIL
bar と baz の末尾で、お互いを CALL で呼び出すのではなく無条件ジャンプ JMP でジャンプしています。相互再帰が最適化されて、これも「無限ループ」になります。くれぐれも実行しないように注意してくださいね。