# Recursive drawing, command flow

I am trying to recursively draw Ck x Ck, where Ck is the k-th iteration of a Cantor set. I have a command which recursively calls itself four times. If I pass N as parameter #6, the output should be 4N little squares. But it only works for N = 1, 2. If I do anything higher, I only get 4 squares, spaced out in the four corners. They are the right size, but there aren't enough of them.

Apparently, the problem has something do with \pgfmathtruncatemacro\C{#6 - 1}. As a test I inserted \draw (0,0) circle (#6); right before this line, and then right after this line, and the output was NOT always the same. It seems that \pgfmathtruncatemacro\C{#6 - 1} somehow changes the value of #6 (in the SAME level of recursion), but I don't see why.

\usepackage{tikz, pgf, ifthen}

\newcommand\cantorsquare[6]{ %x y x y coordinates, dissection coordinates, nesting
%the coordinates are listed in the same order as coordinates for a rectangle
\ifthenelse{#6 = 0} %base case
{
\fill (#1, #2) rectangle (#3, #4);
}
{
{
%find the coordinates for the first smaller square
\pgfmathsetmacro\A{#1 + (1 - #5) * (#3 - #1) / 2}
\pgfmathsetmacro\B{#2 + (1 - #5) * (#4 - #2) / 2}
\pgfmathtruncatemacro\C{#6 - 1}
\cantorsquare{#1}{#2}{\A}{\B}{#5}{\C}
}
{
\pgfmathsetmacro\A{#1 + (1 - #5) * (#3 - #1) / 2}
\pgfmathsetmacro\B{#4 - (1 - #5) * (#4 - #2) / 2}
\pgfmathtruncatemacro\C{#6 - 1}
\cantorsquare{#1}{\B}{\A}{#4}{#5}{\C}
}
{
\pgfmathsetmacro\A{#3 - (1 - #5) * (#3 - #1) / 2}
\pgfmathsetmacro\B{#2 + (1 - #5) * (#4 - #2) / 2}
\pgfmathtruncatemacro\C{#6 - 1}
\cantorsquare{\A}{#2}{#3}{\B}{#5}{\C}
}
{
\pgfmathsetmacro\A{#3 - (1 - #5) * (#3 - #1) / 2}
\pgfmathsetmacro\B{#4 - (1 - #5) * (#4 - #2) / 2}
\pgfmathtruncatemacro\C{#6 - 1}
\cantorsquare{\A}{\B}{#3}{#4}{#5}{\C}
}
}
}

\begin{document}
\begin{tikzpicture} \cantorsquare{0}{0}{5}{5}{0.3}{3} \end{tikzpicture}
\end{document}

-
If for Cantor set you mean a Cantor switching fabric, then I believe you might have a look to the sa-tikz package (where sa stands for switching architectures). Cantor Networks indeed are are just m parallel Benes Networks, and sa-tikz exploits an embedded algorithm to deal with such recursion (more details in the appendix of the documentation). Indeed it's quite easy to draw the modules, but having automatically the interconnections it's a bit complicated and notice that the algorithm works for any dimension of the network. –  Claudio Fiandrino Oct 8 '13 at 6:22
@ClaudioFiandrino Having looked at the output, I suspect David means this: en.wikipedia.org/wiki/Cantor_set –  Loop Space Oct 8 '13 at 7:54
@AndrewStacey: ops... I might have given a check first, but anyway: perhaps I'll remove my answer later, but it was useful as now I have in mind how to extend the library to draw Cantor Networks ;) –  Claudio Fiandrino Oct 8 '13 at 7:59

I agree with Michael's analysis: that it is a problem of expansion. When you pass \C as the sixth element then #6 gets replaced in the macro body by \C so if \C changes then so does the ultimate value of #6. In particular, when you do \pgfmathtruncatemacro\C{#6 - 1} then you are redefining #6.

Having said that, I'm not sure where the expansion is going wrong because you've correctly grouped your recursive calls so modifications to \C in one iteration shouldn't affect others. Moreover, when I run your code then I get the answer that I expect to see. So I have a suspicion that this is an issue with an old version of PGF making a global assignment where it should make a local one. What version of PGF are you using?

I find that LaTeX3 has lots of useful stuff that helps sort out these issues of expansion. In particular, it is possible to ensure that the value of a macro is passed, not the macro itself. So here is your code rewritten in LaTeX3. By passing values rather than macros, I can avoid having to group the recursive calls.

\documentclass{article}
%\url{http://tex.stackexchange.com/q/136907/86}
\usepackage{tikz}
\usepackage{xparse}

\ExplSyntaxOn

\cs_new_nopar:Npn \cantor_sq:nnnnnn #1#2#3#4#5#6
{
\int_compare:nTF {#6 = 0}
{
\fill (\fp_to_decimal:n {#1},\fp_to_decimal:n {#2}) rectangle (\fp_to_decimal:n {#3},\fp_to_decimal:n {#4});
}
{
%find the coordinates for the first smaller square
\fp_set:Nn \l_tmpa_fp {#1 + (1 - #5) * (#3 - #1) / 2}
\fp_set:Nn \l_tmpb_fp {#2 + (1 - #5) * (#4 - #2) / 2}
\int_set:Nn \l_tmpa_int {#6 - 1}
\cantor_sq:nnVVnV {#1}{#2} \l_tmpa_fp \l_tmpb_fp {#5} \l_tmpa_int

\fp_set:Nn \l_tmpa_fp {#1 + (1 - #5) * (#3 - #1) / 2}
\fp_set:Nn \l_tmpb_fp {#4 - (1 - #5) * (#4 - #2) / 2}
\int_set:Nn \l_tmpa_int {#6 - 1}
\cantor_sq:nVVnnV {#1} \l_tmpb_fp \l_tmpa_fp {#4}{#5} \l_tmpa_int

\fp_set:Nn \l_tmpa_fp {#3 - (1 - #5) * (#3 - #1) / 2}
\fp_set:Nn \l_tmpb_fp {#2 + (1 - #5) * (#4 - #2) / 2}
\int_set:Nn \l_tmpa_int {#6 - 1}
\cantor_sq:VnnVnV \l_tmpa_fp {#2}{#3} \l_tmpb_fp {#5} \l_tmpa_int

\fp_set:Nn \l_tmpa_fp {#3 - (1 - #5) * (#3 - #1) / 2}
\fp_set:Nn \l_tmpb_fp {#4 - (1 - #5) * (#4 - #2) / 2}
\int_set:Nn \l_tmpa_int {#6 - 1}
\cantor_sq:VVnnnV \l_tmpa_fp \l_tmpb_fp {#3}{#4}{#5} \l_tmpa_int
}
}

\cs_generate_variant:Nn \cantor_sq:nnnnnn {nnVVnV,nVVnnV,VnnVnV,VVnnnV}

\DeclareDocumentCommand \cantorsquare { m m m m m m }
{
\cantor_sq:nnnnnn {#1}{#2}{#3}{#4}{#5}{#6}
}

\ExplSyntaxOff

\begin{document}
\begin{tikzpicture}
\cantorsquare{0}{0}{5}{5}{0.3}{3}
\end{tikzpicture}

\begin{tikzpicture}
\cantorsquare{0}{0}{5}{5}{0.3}{6}
\end{tikzpicture}
\end{document}


That the small rectangles don't look uniform is an artefact of the rendering as can be seen by looking at a larger zoom.

-

EDIT: Added lualatex version below.

As already pointed out, expansion is the issue, and is easily corrected. However, here is a different solution that requires the very latest PGF/TikZ CVS version.

\documentclass[border=0.125cm]{standalone}
\usepackage{tikz}
\usetikzlibrary{math}

\begin{document}

\begin{tikzpicture}

\tikzmath{
function cantorsquare(\x, \y, \s, \f, \d) {
if (\d == 0) then {
{ \fill (\x, \y) rectangle ++(\s, \s); };
} else {
\u1 = \f*\s;
\u2 = (1-\f)*\s;
cantorsquare(\x, \y, \u1, \f, \d-1);
cantorsquare(\x+\u2, \y, \u1, \f, \d-1);
cantorsquare(\x, \y+\u2, \u1, \f, \d-1);
cantorsquare(\x+\u2, \y+\u2, \u1, \f, \d-1);
};
};
\S = 5;
for \d in {0,...,5}{
\x = int(\d/3) * (\S+1);
\y = mod(\d,3) * (\S+1);
{ \draw (\x-0.1, -\y-0.1) rectangle ++(\S+0.2,\S+0.2); };
cantorsquare(\x, -\y, \S, 1/3, \d);
};
}

\end{tikzpicture}

\end{document}


And here is a version using lualatex which does not require the latest CVS, and is much faster.

\documentclass[border=0.125cm]{standalone}
\usepackage{tikz}

\directlua{
function cantorsquare(x, y, s, f, d)
local u1, u2
if d == 0 then
tex.print("\noexpand\\fill (" .. x .. "," .. y .. ") rectangle ++(" .. s .. "," .. s .. ");")
else
u1 = f*s
u2 = (1-f)*s;
cantorsquare(x, y, u1, f, d-1)
cantorsquare(x+u2, y, u1, f, d-1)
cantorsquare(x, y+u2, u1, f, d-1)
cantorsquare(x+u2, y+u2, u1, f, d-1)
end
end
}

\begin{document}

\begin{tikzpicture}

\foreach \d [evaluate={\S=5; \x=int(\d/3)*(\S+1); \y=mod(\d,3)*(\S+1);}] in {0,...,5}{
\draw (\x-0.1, -\y-0.1) rectangle ++(\S+0.2,\S+0.2);
\directlua{cantorsquare(\x, -\y, \S, 1/3, \d)}
}
\end{tikzpicture}

\end{document}


The result is the same as before.

-

I do not know the details of the packages you are using so it is hard for me to be categorical but it seems you are tripped by the fact that macros passed as arguments are not expanded when the call is performed, but only later when the replacement text where they appear is processed. This may break your recursion. To verify this, you may execute your code with \tracingmacros=1.

You can use registers to force expansion, replacing your usage

\cantorsquare{#1}{#2}{\A}{\B}{#5}{\C}


by

\begingroup
\let\cantorsquare=0\relax % Freeze expansion in edef
\count0=\A\relax
\count2=\B\relax
\count4=\C\relax
\toks0={#1}%
\toks2={#2}%
\toks4={#5}%
\edef\next{%
\cantorsquare{\the\toks0}{\the\toks2}{\the\count0}{\the\count2}{\the\toks4}{\the\count4}%
}%
\expandafter
\endgroup
\next


It prepares a “call” to cantorsquare where \A etc. are replaced by their replacement text — assuming these are numbers. You should edit accordingly each of your four calls.

Note that TeX is a very special computer language, because it does not work with functions and the like, rather, it offers you the possibility to write the sequel of the program—this is what macros are for. If you want to write sophisticated programs in TeX, it is much easier to learn about registers, \edef etc.

Does it help?

Edit: As a side note, I definitely recommand you to have a look at METAPOST if you are interested in programatically generating graphics! It is an awesome piece of software—which just as fun to program as TeX is.

-
Thanks! When I simply put the expressions into the command, it gave me a "missing number" error, but writing them as macros removed the error. So I assumed it must actually be evaluating the expressions. What exactly does setting the macro do? –  David Jekel Oct 8 '13 at 7:41
Setting the macro does very little: it defines a new word in TeX's voabulary (a new escape sequence) and associate it to the replacement text you provide. If you are not familiar with macros and replacement texts (which are very different from functions in programming languages) you could read the relevant chapter in the TeXbook, experiment with the \tracingmacros=1 setting (see the log file of your job) or learn M4, which is also based on macros and replacement text—but much simpler as TeX. –  Michael Grünewald Oct 8 '13 at 10:47

I don’t know the exact specification of this thing but here’s a recursive attempt with append after command (a previous version used path picture but that only works good with rectangular shapes).

## Code

\documentclass[tikz]{standalone}
\usetikzlibrary{calc}
\tikzset{
if/.code n args={3}{% forest.sty
\pgfmathparse{#1}%
\ifnum\pgfmathresult=0 \pgfkeysalso{#3}\else\pgfkeysalso{#2}\fi},
cantorsquare/.style n args={3}{% #1 = current leve, #2 = max level, #3 = factor
if={#1==#2}{cantorsquare end}{cantorsquare go on={#1+1}{#2}{#3}}},
every cantorsquare/.style={shape=rectangle, outer sep=+0pt, ultra thin},
cantorsquare end/.style={every cantorsquare, fill},
cantorsquare go on/.style n args={3}{
every cantorsquare,
append after command={
\pgfextra{\let\myTikzlastnode\tikzlastnode}
let \p{@dim}=($(\myTikzlastnode.north east)-(\myTikzlastnode.south west)$) in
[next nodes/.style={inner sep=+0pt, outer sep=+0pt, minimum width=(#3)*\x{@dim},
minimum height=(#3)*\y{@dim}, cantorsquare={#1}{#2}{#3}}]
node [next nodes, above right] at (\myTikzlastnode.south west) {}
node [next nodes, above left]  at (\myTikzlastnode.south east) {}
node [next nodes, below right] at (\myTikzlastnode.north west) {}
node [next nodes, below left]  at (\myTikzlastnode.north east) {}}}}
\begin{document}
\foreach \lev in {1, ..., 5, 4, 3, 2}{
\begin{tikzpicture}
\node[cantorsquare/.expanded={1}{\lev}{.3333}, minimum size=2cm] {};
\end{tikzpicture}}
\foreach \lev in {1, ..., 5, 4, 3, 2}{
\begin{tikzpicture}[every cantorsquare/.append style={shape=circle},
every cantorsquare/.append style=draw]
\node[cantorsquare/.expanded={1}{\lev}{.3333}, minimum size=2cm] {};
\end{tikzpicture}}
\end{document}


-