末尾再帰というのは、文字通り「末尾で再帰呼出を行う」ことである。もう少しちゃんと言うと、関数の中で、最後に実行（評価）されるのが当該の関数自身の呼出（適用）であり、かつその呼出（適用）の戻り値（評価値）が元の関数実行の戻り値（評価値）になっている形のことをいう。
例えば、以下の Lua コードにおいて、path_field 関数の中にある再帰呼出は末尾再帰になっている。
function path_field (obj, flds) if #flds == 0 then return obj else return path_field(obj[flds[1]], {unpack(flds, 2)}) -- + 0 end end
ちなみに、この関数は、例えば path_field(t, {'a', 'b'}) に対して、t.a.b の値を返すという動作をする。(({unpack(flds,2}} はリスト flds の先頭要素を除去した（別の）リスト。Perl でいえば [@$flds[1,$#$flds]] に相当する。))
t = {l={l=1,r={l=2,r=3}},r={l=4,r=5}} print(path_field(t, {'l', 'r', 'l'})) --> 2 (=t.l.r.l) を出力する
わざわざこの形に名前がついているのには理由がある。通常、関数呼出では呼出元の関数の実行文脈の情報（局所変数や実行ポインタの戻り先アドレス、等）を保存する必要があるので、多重の関数呼び出しをするとそれだけの記憶領域を消費することになる。ところが、「末尾」再帰の場合、呼び出し元の文脈は（実行を終えているので）もはや不要になるので、処理系内部で、これを関数の先頭へのジャンプに置き換えるという「最適化」を行うことで、先述の余分な記憶領域消費を無くすことができるのである。要するに、末尾再帰ならば、関数呼出のネストが多重になってもメモリを無駄遣いしないということである。これを「末尾再帰最適化」と呼ぶ。*1
もちろん、末尾再帰最適化が行われるかどうかは処理系に依存する。ところで、再帰呼出のメモリの無駄遣いは、繰り返し処理を専ら再帰呼び出しで実現する―つまり、100万回のループがあると100万重の関数呼出となる―関数型プログラミング言語で特に問題となる。従って、多くの関数型プログラミング（Scheme、OCaml、Haskell、等）では、末尾再帰最適化の実装が言語規定に入っている。Lua は関数型言語ではないが、末尾再帰最適化を行う。これは、故意にエラーを起こしてスタックトレースを見ればよく解る。
-- (対話モード)
-- t.l.x は nil だから nil.y を得ようとしてエラー
> print(path_field(t, {'l', 'x', 'y'}))
test.lua:3: attempt to index local 'obj' (a nil value)
stack traceback:
test.lua:3: in function <test.lua:1>
(tail call): ? ← 最適化されたこと
(tail call): ? ← を表している
stdin:1: in main chunk
[C]: ?ここで、元のプログラムの 2 行目の「+ 0」のコメントアウトを外すと、再帰呼出が末尾再帰ではなくなる。これで同じ呼出を行ってみる。
> print(path_field(t, {'l', 'x', 'y'}))
test.lua:3: attempt to index local 'obj' (a nil value)
stack traceback:
test.lua:3: in function 'path_field'
test.lua:3: in function 'path_field' ←多重呼出がスタック
test.lua:3: in function 'path_field' ←に記録されている
stdin:1: in main chunk
[C]: ?というわけで、ようやく TeX の話になる。TeX は「条件分岐以外の全ての実行制御をマクロ展開で行う」という特異な性質を持っている。だから当然繰り返し処理もマクロの再帰呼出（展開）で行うことになる。以下は無限ループになる例である。
\def\endless{Hello the wheel!\par\endless}
\endless\bye1 行目ではマクロ \endless を定義している。2 行目に入って、今定義した \endless が展開される。これ以降の入力トークンバッファの変化を追ってみる。*2
\endless\bye …(1) ↓ Hello the wheel!\par\endless\bye …(2)
次の「H」はマクロではないので展開ではなく「実行」される―つまり文字 H が現在の段落に出力される。
↓ ello the wheel!\par\endless\bye …(3)
次の「e」も同様に「実行」され、以後「l」「l」と同様に続く。そして、「\par」を「実行」すると、現在の段落がページに出力される。その後の状態は次のようになる。
↓ \endless\bye …(4)
この (4) は (1) と同じである。つまり、「Hello the wheel!」という段落を「出力」したということを除いて、過去の状態と全く同じ状態に戻っているのである。TeX 言語（少し簡略化されているが）では、「実行文脈」が入力トークン列の状態しかない。TeX で「現在、マクロが何重に呼び出されているか」という問いは意味を持たないであろう。*3結果的に、「最適化」をしなくても、最初から「末尾再帰」は記憶領域を消費しないのである。((これも、実際には、「出力された段落」がメモリを消費しないかを考える必要がある。段落のデータはメモリ上に溜まっていくのだが、1 ページの分量を超えると、それはページとなって DVI ファイルに吐き出されてメモリからは消える。従って、例のプログラムは「ファイルの大きさが限界に達する」（ハードディスクの容量を食い尽くす等）まで実際に動き続けるようである。（いや待てよ、ページ番号（\count0）がオーバーフローするか？）))
うわっ、間違えて途中で公開してしまった。続きはまた後日。
