前回において、「TeX マクロの再帰呼出が末尾再帰になる場合」の展開の様子について考察した。ここから、TeX での「末尾再帰」の定義を導くことができる―すなわち、TeX マクロの置換テキスト（展開した内容）の処理（プリミティブの実行や他のマクロの展開）において、最後に行われるものが当該マクロの展開である場合、それ（マクロの呼出）が「末尾再帰」である。
TeX の末尾再帰に関して注意すべきなのは、普通のプログラミング言語だと末尾再帰になりそうな形が TeX ではならないことがあるということである。
例えば、1 から指定の数まで順に整数を出力する*1という典型的な繰り返し処理を実装してみる。
% \countUpTo{<n>}: 1 から n までの整数を(改段落しながら)出力する
\newcount\num
\newcount\limitNum
\def\countUpTo#1{%
\num=0 \limitNum=#1\relax
\countUpToIter
}
\def\countUpToIter{%
\advance\num1
\the\num\par % \num の値を数字で出力して改段落
\ifnum \num<\limitNum % 指定値に達していないなら
\countUpToIter % 末尾再帰(?)を行う
\fi
}これで \countUpTo{40} とすると確かに正常に動く。私の環境では \countUpTo{1000} でも大丈夫だった。しかし、\countUpTo{10000} は「容量超過」のエラーになってしまう。前回調べたように、末尾再帰になっていれば何回でも反復できるはずなので、この結果は末尾再帰になっていないことを意味する。
! TeX capacity exceeded, sorry [input stack size=5000].
<inserted text> 4
998
\countUpToIter ->\advance \num 1 \the \num
\par \ifnum \num <\limitNum \coun...
\countUpToIter ... \num <\limitNum \countUpToIter
\fi
\countUpToIter ... \num <\limitNum \countUpToIter
\fi
\countUpToIter ... \num <\limitNum \countUpToIter
\fi
\countUpToIter ... \num <\limitNum \countUpToIter
\fi
...
l.15 \countUpTo{10000}何故 \countUpToIter 中での自身の呼出は「末尾」でないのか。実は理由は非常に簡単である。
本当に末尾にあるのは \fi であるから。
TeX の if 文はマクロと同様に「展開」することで評価される。その仕組みについては、既に「条件文における「展開」」の記事で説明した。ポイントは、条件部を表す\if... トークンだけでなく、\else や \fi も「展開」によって処理されるということである。つまり、今の \countUpToIter の末尾の
\ifnum\num<\limitNum\countUpToIter\fi
の条件成立時の展開結果がもし
↓
\countUpToIter
となる*2のであれば、末尾再帰が成立するのであるが、実際の展開結果は以下のようになる。そして、実行器の「条件分岐状態」が更新される（ネストレベルが増加する）。
↓
\countUpToIter\fi
この深くなったネストレベルから脱出するには \fi を展開する必要があるのだが、実際には次に起こるのは \countUpToIter の展開である。
↓
\advance\num1\the\num\par\ifnum\num<\limitNum\countUpToIter\fi\fi
↓
………
↓
\countUpToIter\fi\fi
↓
………
↓
\countUpToIter\fi\fi\fi
このようにして、終了条件が満たされるまで、後ろにある \fi が延々と増えていってしまう。繰り返し回数が非常に大きくなったら、何かが破綻するということは容易に想像できるだろう。*3再帰呼出はほぼ確実に if が伴うが、*4それを普通に書いたのでは末尾再帰にならないのである。
では if 文がある場合にどうすれば末尾再帰が実現できるか。これには色々な方法がある。原理が判りやすいのは、マクロを介して本当に「末尾」に再帰呼出を置くようにする方法である。
\ifnum \num<\limitNum \def\next{\countUpToIter}%
\else \def\next{}%
\fi
\next
終了条件が不成立（つまり \ifnum が成立）ならば、末尾にある \next は \countUpToIter に展開されるので、「末尾で再帰呼出する」ことが実現できる。終了条件成立ならば、\next は何もしないのでそこで「大本の \countUpTo{<n> の実行が終わる」ことになる。これは現実の TeX プログラミングでよく使われる方法である。((\def の代わりに \let を用いて、\let\next\countUpToIter／\let\next\relax と書いても同じことになる。))
今回の場合のように、再帰呼出が単一トークン（マクロ引数がない）である場合は、次の形も使える。
\ifnum \num<\limitNum
\expandafter\countUpToIter
\fi
これだと、\countUpToIter の先に \fi が「展開」される―つまり if 条件を脱出して \fi が無くなる。その後の状態では確かに \countUpToIter が「末尾」にある。この形式は代入を使わないので、完全展開可能が要求される繰り返し処理で使われる。ただし、再帰呼出が単一トークンでない、あるいはそもそも if がネストしている場合には、大量の \expandafter を書く羽目に陥るのであまりやりたくない。完全展開可能なように複数トークンの再帰呼出を行うには、例えば次のような方法がある。
% まずこれを定義する（LaTeX では定義済である）
\def\@gobble#1{}
\def\@firstofone#1{#1}
% 引数付のマクロで末尾再帰したい
\def\foo#1{%
...... % 何か処理を行う
\if<終了条件> \expandafter\@gobble
\else \expandafter\@firstofone
\fi {\foo{...}}%
}
展開過程を辿っていくと、非終了時には \foo{...} が末尾に来ることが判る。
