# Strange recursive macro output

Strange recursive macro output

The code that follows describes a macro that can iterate recursively (i.e, a forloop) and uses e-TeX numexpr. It is based on an example found in the e-TeX manual (page 9)

The first part of the code is pretty straight forward. In the second definition of foo, it appears that the macro loops twice!

0,1,2,3,4,5
TeX
TeX
TeX
TeX
TeX


Something does not look correct here! It reminds me of closures in JavaScript. Can you explain this behaviour?

There is also a second part to the question. The e-TeX manual defines a similar function as:

\def\foo#1#2{\noindent\number#1
\ifnum#1<#2,
\expandafter\foo
\expandafter{\number\numexpr#1+1\expandafter}%
\expandafter{\number#2\expandafter}%
\fi}


What are all these \expandafters used for? They seem unecessary. Shouldn't also the comma be after \number#1 on line one rather than after the ifnum?

Here is my code with all three examples:

\documentclass[11pt]{article}
\begin{document}

\def\foo#1#2#3{\noindent\number#1, \TeX\par
\ifnum#1<#2
\foo{\number\numexpr#1+\number#3}{\number#2}{\number#3}%
\fi}

\foo{0}{5}{1}
\bigskip

\def\foo#1#2#3{\noindent\number#1,
\ifnum#1<#2
\foo{\number\numexpr#1+\number#3}{\number#2}{\number#3}%
%\else\relax

\noindent\TeX\par
\fi}

\foo{12}{18}{1}

\bigskip
\def\foo#1#2{\number#1, \TeX\par
\ifnum#1<#2
\expandafter\foo
\expandafter{\number\numexpr#1+1\expandafter}%
\expandafter{\number#2\expandafter}%
\fi}

\foo{12}{18}

\end{document}

-
I remembered stumbling upon a TUGboat article recently, maybe it can be of help: tug.org/TUGboat/Articles/tb29-2/tb92jackowski.pdf – morbusg Nov 3 '10 at 19:35
@morsburg Thanks for the link – Yiannis Lazarides Nov 3 '10 at 19:49
may I suggest that you give different names (\fooa, \foob etc would be okay) to the different version of \foo, so that it's easier to refer to them? Including a name for "the second version of \foo with \else\relax uncommented", please :-) Also, I'm not sure I understand: do you expect the second version of \foo to give the same result as the first one? – mpg Nov 4 '10 at 0:41
@mpg Thanks. I guess is too late to rename them. – Yiannis Lazarides Nov 4 '10 at 1:48

For now, I'll answer only your second question, about the example from e-TeX. The \expandafter are used to force TeX to actually do the computation before calling \foo recursively, and to clear the finale \fi so that the recursion is terminal. This isn't strictly necessary but is an optimisation. Here is a way to visually check my first assertion:

\documentclass{minimal}

\def\foo#1#2{\noindent\number#1
\ifnum#1<#2,
\expandafter\foo
\expandafter{\number\numexpr#1+1\expandafter}%
\expandafter{\number#2\expandafter}%
\fi}

\def\noexpfoo#1#2{\noindent\number#1
\ifnum#1<#2,
\noexpfoo
{\number\numexpr#1+1}%
{\number#2}%
\fi}

\begin{document}

\tracingmacros1
\foo{1}{5}
\noexpfoo{1}{5}
\tracingmacros0

\end{document}


After compiling this file, look at the log. You can check that the last call of \foo has arguments 5 and 5, while the last call to \noexpfoo has \number \numexpr \number \numexpr \number \numexpr \number \numexpr 1+1+1+1+1 as its first argument, which is essentially a representation of 5 in base one, as opposed to its base ten representation used in the \expandafter case. The size of the first argument grows exponentially in the no-expandafter case. This is very bad and will make TeX crash due to lack of memory, or at least run very slowly, for big loops.

Clearing the final \fi serves the same purpose of making the macro more scalable, in a different way. Without the final \expandafter in the definition of \foo, at the final call, TeX's input stack would look like \foo{5}{5}\fi\fi\fi\fi\fi, with all the associated information about with macro call the different \fi are coming from. With the final \expandafter (indirectly triggered by the first one), the input stack looks like \foo{5}{5} without any trailing \if.

I'm not including more details about \expandafter chaining and the way conditionals expand to keep the answer focused, but feel free to ask if needed.

Also, the comma is after the \ifnum test so that you get 1, 2, 3, 4, 5 without a trailing comma-space as in 1, 2, 3, 4, 5,.

Complement about expansion. So, in the definition of \foo there are 5 \expandafters and three \numbers. The first \expandafter expands whatever there is after \foo, which happens to be the second \expandafter, which in turns expands what follows the brace, ie the second \number (the first one is earlier in the macro). Now, \number tries to read a number expanding everything until it finds something that doesn't belong to a number. Here the right brace will stop that process, but it won't be hit until the third \expandafter is expanded, which triggers the fourth \expandafter, which in turn triggers the last \number which, in the course of processing everything up to the closing brace, triggers the next \expandafter, which expands whatever comes after the brace, which is... wait for it... \fi.

Now, a common misconception about how TeX handles (expands) conditionals is to forget that the \fi is still here. When TeX expands the \ifnum, it doesn't read everything up to the \fi. That's what a macro would do with its arguments: read them entirely. But branches of conditionals are not macro arguments. Instead, when expanding \ifnum and seeing it is true, TeX just continues reading the rest, making a note to self that the next \fi encountered is completely normal and should be silently expanding to nothing. If it encounters a \else first, then is will ignore it and everything up to (and including) the closing \fi. So, only ignored branches are treated as a block.

-
Great answer mpg. So essentially the reason for the expandafters is to optimize the code. Would appreciate if you could add a comment or two as to how the expansion work, especially the \expandafter}\fi} part – Yiannis Lazarides Nov 4 '10 at 2:18
I added to paragraphs about that. I hope it doesn't bloat the answer too much. – mpg Nov 4 '10 at 13:11
In the paragraph right after the code listing, do you mean \noexpfoo instead of \foobar? – Willie Wong Nov 4 '10 at 14:13
@Willie: right, thanks for spotting that. I edited the answer to fix it. – mpg Nov 4 '10 at 14:48

Now, concerning your first question. There is no double recursion going on. You seem to believe the macros recurse-loops to print 1, 2, 3, 4, 5 and the recurse-loops again to print all the TeXs. The truth is, there is only one recursion, but the final TeX are kept on a pile and poped at the end of the recursion. That is, when the final call to \foois made, TeX's input stream looks like \foo{arg1]{arg2}{arg3}\noindent\TeX\par\noindent\TeX\par\ETC.

Here is an example that makes it more visual by changing the output color at each invocation of \fooX.

\documentclass{article}
\usepackage{xcolor}

\newcommand\nbcolor[2]{%
\color{green!\number\numexpr(#2-#1)*100/#2\relax!blue}}

\def\fooa#1#2#3{
\begingroup \nbcolor{#1}{#2}%
\noindent\number#1, \TeX\par
\ifnum#1<#2
\fooa{\number\numexpr#1+\number#3}{\number#2}{\number#3}%
\fi \endgroup}

\def\foob#1#2#3{%
\begingroup \nbcolor{#1}{#2}%
\noindent\number#1,
\ifnum#1<#2
\foob{\number\numexpr#1+\number#3}{\number#2}{\number#3}%

\noindent\TeX\par
\fi \endgroup}

\def\fooc#1#2#3{
\begingroup \nbcolor{#1}{#2}%
\noindent\number#1,
\ifnum#1<#2
\fooc{\number\numexpr#1+\number#3}{\number#2}{\number#3}%
\else\relax

\noindent\TeX\par
\fi \endgroup}

\begin{document}

\fooa{0}{5}{1} \bigskip
\foob{0}{5}{1} \bigskip
\fooc{0}{5}{1} \bigskip

\end{document}


I hope it makes it clearer that \foob loops only once. The last \TeX remains from the first call to \foob, the last-but-one from the second, etc.

By the way, this has nothing to do with TeX, it's a general fact with recursion: you don't get the same result depending on the relative place of the recursive call and the rest of the code.

-
Thanks. If you remove the empty line at fooc, between \else\relax and \noindent\TeX the output changes. This is difficult to understand. – Yiannis Lazarides Nov 4 '10 at 2:26
@Yiannis: The empty line gives you the paragraph break, which is the normal TeX behaviour. – Hendrik Vogt Nov 4 '10 at 9:55

Not sure what you want to happen but if you change the second example to

\def\foo#1#2#3{\noindent\number#1,\TeX\par
\ifnum#1<#2
\foo{\number\numexpr#1+\number#3}{\number#2}{\number#3}%
\fi}

\foo{12}{18}{1}


you will get

12, TeX

13, TeX

14, TeX

15, TeX

16, TeX

17, TeX

18, TeX

For the last example, you can judge for yourself if the \expandafters are necessary by taking them out and seeing what happens. Essentially the \ifnum will get evaluated not on a number but on \number\numexpr#1+1, which it won't know how to resolve. You get an infinite loop.

-
If you uncomment the \else\relax on the second example the behaviour goes back to normal. I am trying to understand how the second loop got created. Please check the output to see what happens. None of the two examples I listed used \expandafter' and I was wondering if it was possible for the e-TeX example to also be written to avoid these. Thanks for the answer – Yiannis Lazarides Nov 3 '10 at 19:48
Oh, I see. Sorry to answer prematurely. I'll have to look more carefully at it. – Matthew Leingang Nov 3 '10 at 22:37
I disagree about \ifnum\number\numexpr`: it's perfectly valid and works. – mpg Nov 4 '10 at 0:15
@mpg: I agree with your disagreement. I should edit my answer but I might just upvote yours. – Matthew Leingang Nov 4 '10 at 2:34