# How to make a recursive macro in (La)TeX?

The following MWE is the code of my attempt translating my working algorithm in C# to (La)TeX. I don't understand why it does not work. Can you probe the source of problem?

Remarks:

1. #1 is a list of binary elements. Either character 1 (move upward) or 0 (move to the right) will be appended to this list recursively. In the beginning it is an empty list.
2. #2 represents the remaining number of movements to the right.
3. #3 represents the remaining number of movements upward.
\documentclass{article}
\usepackage{ifthen,pgf}

\parindent=0pt

\newcommand{\Populate}[3]%
{%
\ifthenelse{#2=0}% on the most left border?
{%
\ifthenelse{#3=0}% on the most top border?
{%
#1\endgraf% I need to trim the most left comma later!
}%
{%
% move upward
\pgfmathtruncatemacro{\ups}{#3-1}%
\Populate{#1,1}{#2}{\ups}%
}%
}%
{%
\ifthenelse{#2=#3}% on the diagonal border?
{%
% move to the right
\pgfmathtruncatemacro{\rights}{#2-1}%
\Populate{#1,0}{\rights}{#3}%
}%
{%
% move to the right
\pgfmathtruncatemacro{\rights}{#2-1}%
\Populate{#1,0}{\rights}{#3}%
% move upward
\pgfmathtruncatemacro{\ups}{#3-1}%
\Populate{#1,1}{#2}{\ups}%
}%
}%
}

\begin{document}
\Populate{}{4}{4}
\end{document}


It produced a wrong output as follows:

,0,0,0,0,1,1,1,1
,0,0,0,1,1,1,1
,0,0,1,1,1,1
,0,1,1,1,1


The expected output must be as follows: (the leading comma will be removed later)

,0,0,0,0,1,1,1,1
,0,0,0,1,0,1,1,1
,0,0,0,1,1,0,1,1
,0,0,0,1,1,1,0,1
,0,0,1,0,0,1,1,1
,0,0,1,0,1,0,1,1
,0,0,1,0,1,1,0,1
,0,0,1,1,0,0,1,1
,0,0,1,1,0,1,0,1
,0,1,0,0,0,1,1,1
,0,1,0,0,1,0,1,1
,0,1,0,0,1,1,0,1
,0,1,0,1,0,0,1,1
,0,1,0,1,0,1,0,1


The last edit:

For N x N case, use \Populate{0}{N-1}{N} to avoid having an extra job to remove the leading commas above. (I just got this enlightenment)

-
Are you sure that tikz-pgf tag is necessary? ;-) – Paul Gaborit Jul 18 '12 at 7:10
@PolGab: Maybe because of its scope behavior. :-) – kiss my armpit Jul 18 '12 at 7:16

## 2 Answers

You have to use more groups ({...}) to localize (re)definition of your macros \ups and rights:

\documentclass{article}
\usepackage{ifthen,pgf}

\parindent=0pt

\newcommand{\Populate}[3]%
{%
\ifthenelse{#2=0}% on the most left border?
{%
\ifthenelse{#3=0}% on the most top border?
{%
#1\endgraf% I need to trim the most left comma later!
}%
{%
% move upward
\pgfmathtruncatemacro{\ups}{#3-1}%
\Populate{#1,1}{#2}{\ups}%
}%
}%
{%
\ifthenelse{#2=#3}% on the diagonal border?
{%
% move to the right
\pgfmathtruncatemacro{\rights}{#2-1}%
\Populate{#1,0}{\rights}{#3}%
}%
{%
{% GROUP
% move to the right
\pgfmathtruncatemacro{\rights}{#2-1}%
\Populate{#1,0}{\rights}{#3}%
}%
% move upward
\pgfmathtruncatemacro{\ups}{#3-1}%
\Populate{#1,1}{#2}{\ups}%
}%
}%
}

\begin{document}
\Populate{}{4}{4}
\end{document}


Remark: a macro is not a function. Your question should be "How to make a recursive macro in (La)TeX?".

-
I prefer the control words \bgroup and \egroup to the curly braces { and } because I can avoid appending % and too deep nested scoping. – kiss my armpit Jul 18 '12 at 7:20
@HiggsBoson \bgroup starts a new scope just the same as {. And it is longer than {%. – Ryan Reich Jul 18 '12 at 7:51
@RyanReich: But my eyes locates the scoping pair much better when using \bgroup and \egroup. – kiss my armpit Jul 18 '12 at 8:10

The simplest version I can do. If you have more simpler one, please edit this answer.

\documentclass{minimal}

\newcount\u
\newcount\r

\def\d#1{\advance#1-1\relax}

\newcommand{\Populate}[3]{%
\r#2\u#3%
\ifnum\r=0
\ifnum\u=0\relax
#1\endgraf
\else
\d\u\Populate{#1,1}{#2}{\the\u}%
\fi
\else
\ifnum\r=\u
\d\r\Populate{#1,0}{\the\r}{#3}%
\else
{\d\r\Populate{#1,0}{\the\r}{#3}}% must be grouped!
\d\u\Populate{#1,1}{#2}{\the\u}%
\fi
\fi}

\begin{document}
\Populate{0}{3}{4}
\end{document}

-