5

I'm trying to use recursion to draw Sierpinski's triangle in TikZ. I have something that's partially working, but not quite. At each step, I draw something. Then, if the counter is positive, I call my macro again.

Here's a somewhat simplified example without the TikZ stuff (as I'm fairly certain that's not where my issue is):

\documentclass{article}

\newcounter{mycounter}

\newcommand{\example}[1]{%
  \setcounter{mycounter}{#1}%
  \themycounter%
  \ifnum\themycounter>0%
    [%
    \setcounter{mycounter}{#1}%
    \addtocounter{mycounter}{-1}%
    \example\themycounter%
    ,%
    \setcounter{mycounter}{#1}%
    \addtocounter{mycounter}{-1}%
    \example\themycounter%
    ]%
  \fi%
}
    
\begin{document}

\example4

\end{document}

This is outputting:

4[3[2[1[0,-1],-2],-3],3[2[1[0,-1],-2],-3]]

What I want the output to be is:

4[3[2[1[0,0],1[0,0]],2[1[0,0],1[0,0]]],3[2[1[0,0],1[0,0]],2[1[0,0],1[0,0]]]]

I think my issue is that \setcounter{mycounter}{#1} is expanding to \setcounter{mycounter}{\themycounter}, which is resulting in no change to the value of mycounter, rather than resetting it to what it was at the start of the macro. Is there an easy solution to this? Do I need to learn how \expandafter works?

2 Answers 2

7

If the counters are the problem, remove the counters! :)

\documentclass{article}

\def\sierpinski#1{\number\expandafter\sierpaux\number\numexpr#1;}
\def\sierpaux#1;{%
  \ifnum#1=0 0%
  \else
    \expandafter\sierpauxi\number
      \expandafter\sierpaux\number\numexpr#1-1;;#1%
  \fi}
\def\sierpauxi#1;#2\fi{\fi#2[#1,#1]}

\begin{document}

\sierpinski4

\edef\x{\sierpinski{19}}

\end{document}

The code is a simple recursion of the \sierpaux macro. When the loop starts, it traverses down the numbers, subtracting one, until it finds a zero, at which point the input stream looks like this:

\number\expandafter\sierpauxi
\number\expandafter\sierpauxi
\number\expandafter\sierpauxi
\number\expandafter\sierpauxi 0;1\fi;2\fi;3\fi;4\fi

then the last \sierpauxi kicks in and replaces 0;1\fi by \fi1[0,0], and then the \fi is expanded away and you have:

\number\expandafter\sierpauxi
\number\expandafter\sierpauxi
\number\expandafter\sierpauxi 1[0,0];2\fi;3\fi;4\fi

then again, \sierpauxi kicks in and replaces 1[0,0];2\fi by 2[1[0,0],1[0,0]], rinse and repeat until you are left with the output. Note that it just computed the list of numbers once, then used macro expansion to duplicate everything as needed, so this is O(n).

But the list grows big rather quickly, so the maximum number you can have in the argument is 19.

Here's a much slower version that allows up to 20:

\documentclass{article}

\def\sierpinski#1{\sierpauxi{#1}}
\def\sierpauxi#1{\expandafter\sierpaux\number\numexpr#1;}
\def\sierpaux#1;{%
  \ifnum#1=0 0%
  \else #1\expandafter\sierpauxii\romannumeral-`0\sierpauxi{#1-1};%
  \fi}
\def\sierpauxii#1;{[#1,#1]}

\begin{document}

\sierpinski4

\edef\x{\sierpinski{20}}

\end{document}

This version evaluates both sides of the tree recursively, so it is O(n^2), but it does some more shuffling around that allows you to have a larger input.

5
  • hmm you were a few seconds faster:-) Nov 4, 2021 at 18:40
  • @DavidCarlisle tex.stackexchange.com/questions/503973/… :) Nov 4, 2021 at 18:41
  • Without really understanding how either of your solutions works…it looks like the main difference is \number vs. \expandafter{\the…\relax}. Is the former a shorthand for the latter? I certainly support avoiding global variables, and I had only been using counters because I didn't realize TeX had something like this to use instead.
    – Pi Fisher
    Nov 4, 2021 at 19:18
  • @PiFisher No, \number tells TeX to scan for a number, and \the tells it to expand the value of a register, but that's not the difference. The first code is faster because it evaluates only one branch of the tree and duplicates it, but it takes a bit more memory to do so, thus it only allows up to 19. The second version evaluates every branch, so it's much slower, but takes less memory, so you can go up to 20 without getting an error. Nov 4, 2021 at 19:24
  • 1
    @PiFisher I added some explanation. Nov 4, 2021 at 19:59
7

Your explanation is correct but I think it is simpler not to use counters here especially latex counters which are global, and also use of \themycounter which is the print form and not guaranteed to be suitable for numeric tests.

\documentclass{article}


\newcommand{\example}[1]{%
  \the\numexpr#1\relax
  \ifnum#1>0 %
    [%
    \expandafter\example\expandafter{\the\numexpr#1-1\relax}%
    ,%
    \expandafter\example\expandafter{\the\numexpr#1-1\relax}%
   ]%
  \fi%
}
    
\begin{document}

\example4

\end{document}

this just passes the value directly in #1 without using a register

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .