3

I'd like to trace the recursive calls of some arbitrary function. This includes the stack ``unwinding'' as the activation records are popped off. For reference, here is an example of what I'm after. Ideally, it wouldn't be slanted off to the side like it is in theirs. I'm sure I could figure this out using Tikz, but I doubt it would look nearly as good.

2
  • 2
    Welcome. Are you looking for an automatic version or do you just want to draw a diagram of such a trace? The latter is rather easy. Dec 23, 2022 at 19:57
  • @Qrrbrbirlbel An automated solution would be interesting to test, but all I'm after is a drawing. The TikZ solution seems like it would be incredibly cumbersome to get exactly right. Dec 23, 2022 at 21:00

1 Answer 1

11

As with any TikZ picture … just start somewhere and build it up.

For your picture I'm choosing the chains library which isn't necessarily the most advanced technique to create a diagram that's only about nodes and edges – the graphs library is made for that and has an advanced input syntax – but it is very close to plain TikZ and very easily adaptable.

Its main two functions are

  1. placing multiple nodes according to one rule and
  2. “joining” these nodes (meaning drawing edges between them).

There's nothing in it you can't do with just the positioning library (which itself just provides small shortcuts to relative positioning of nodes) and the edge operation (which itself is already rather powerful).

But we don't have to worry about the edge cases (the very first node can't be joined with a previous node and can't be placed in relation to another node).

With just this small TikZ picture

% preamble:
\usetikzlibrary{arrows.meta, chains}
% document:
\begin{tikzpicture}[
  thick, >={Latex},
  start chain=going above, node distance=5mm,
  every join/.append style=<-,
  function/.style={
    shape=rectangle, draw, minimum width=3cm, rounded corners}
]
\foreach \FACT in {0, ..., 4}
  \node[function, on chain, join]{factorial(\FACT)};
\coordinate[on chain, join];
\end{tikzpicture}

you already get
enter image description here

Halfway there!

Now, we could add another loop that draws the curved paths as such:

\foreach[count=\prevFACT from 1] \FACT in {2, ..., 6}
  \draw[->] (chain-\prevFACT) to[out=5, in=-5, min distance=10mm] (chain-\FACT);

enter image description here

Since I haven't given the chain no name (there's nothing before going) it's named chain and its nodes can be accessed by chain-1, chain-2, etc. The first and the last can be accessed by the name chain-begin and chain-end respectively.

But that's just another join!
Since the last arrow will be a pain to deal with I'll just place an invisible node of the same size at its place.

To generalize this a bit, I'll add a macro that specifies the total number of nodes (+ 1). To implement the invisible node, I'll use node contents to define the contents of the node instead of the {…} syntax which allows me to overwrite the content of a node with another text.

We'll add another join and …

\begin{tikzpicture}[
  thick, >={Latex},
  start chain=going above, node distance=5mm,
  every join/.append style=<-,
  function/.style={
    shape=rectangle, draw, minimum width=3cm, rounded corners},
  return path/.style={out=5, in=-5, ->, min distance=10mm},
]
\newcommand*{\tikzMaxRecursion}{5}
\tikzset{
  function \tikzMaxRecursion/.style={draw=none, node contents=\vphantom{()}}}
\foreach \FACT in {0, ..., \tikzMaxRecursion}
  \node[
    function, node contents={factorial(\FACT)}, function \FACT/.try,
    on chain, join, join=by return path];
\end{tikzpicture}

enter image description here

We will add overlay to the function \tikzMaxRecursion key so that there won't be additional white space at the top of the picture.

Let's add the nodes with the return arrows.
Since the first node will be different I'm using the ext.misc library of my tikz-ext package to place a different edge node with the first connection.

With just a small addition

\foreach \FACT in {0, ..., \tikzMaxRecursion}
  \node[
    function, node contents={factorial(\FACT)}, function \FACT/.try,
    on chain, join,
    join=by {return path,
      /utils/TeX/ifnum={\FACT=1}
        {edge node={node[right] {\textbf{return} 1}}}
        {edge node={node[right] {\textbf{return} calculate \FACT}}}
    }];

we get
enter image description here


At this point, we actually have to think about the recursive element of this diagram or its displayed values.

For this example with simple integer arithmetics, it was much easier to just implement that recursive function in TeX and have TeX actually do all the work.
The \foreach does offer an option to remember values from the previous iteration but here it just seems simple enough. (And for more complex function you might be better off just generating the values outside TeX and just input them raw.)


The gray arrows are not easy. We either have to adjust the starting and endpoint manually or make each return node actually be multiple nodes.

And these edge node are actually five nodes each time. With the special text right anchor ([A], [B]) they are placed in a small row with no space between the text part of the node – basically yet another chain. This works best because the nodes are not transformed. More work is needed then and maybe the subnode of the tikzmark library should be used here.

Two of those labels get a name that is inherited from the chain (\tikzchaincurrent returns the node name of current node on the chain), we can reference them later when drawing the gray arrows.

We could draw these gray arrows now in a separate loop:

\foreach[count=\nextFACT from 3] \FACT in {2, ..., \tikzMaxRecursion}
  \path[return conn, blue] (chain-\FACT-right) edge (chain-\nextFACT-left);

But we can also add yet another join but not for the first two main nodes in the chain (because then we don't have yet two return nodes).


To make this label chain usable with other recursive function, I'll introduce the label row key which uses a \tikzLabelRow parser.

Basically, you give return node a list of parts and if it starts with (<name>) that label gets assigned the name <name>.

For convenience, the macros \tikzRecFrom and \tikzRecTo are setup in a way that you don't have to think about their actual names.


I'll admit, it wasn't as easy as I've expected it to be – apart from the gray arrows, I was fully expecting them to be a pain.

Though, changing the coordinate to a node resolved most of the annoying things to look out for.

Leaving out the gray arrows should make it very easy adaptable for different recursive functions.

Code

\documentclass[tikz]{standalone}
\usepackage{xparse}
\usetikzlibrary{arrows.meta, chains, ext.misc}
% \usepackage{xfp}% for \inteval (alternatively: \pgfinteval)
\makeatletter
\newcommand*{\calcFactorial}[1]{%
  \expandafter\calcFactorial@\expandafter{\inteval{#1}}}
\newcommand*{\calcFactorial@}[1]{%
  \ifnum#1<2 \expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi
  {1}{\inteval{#1*\expandafter\calcFactorial\expandafter{\inteval{#1-1}}}}}
\pgfdeclaregenericanchor{text right}{%
  \pgf@sh@reanchor{#1}{base}%
  \multiply\pgf@x by 2 }
\makeatother
\DeclareDocumentCommand{\tikzLabelRow}{d()u,u\STOP}{%
  \tikzset{
    label={[anchor=text,
      style/.expanded={\IfNoValueF{#1}{name={#1}}},
      /utils/TeX/ifempty={#3}{}{/utils/exec={\tikzLabelRow#3\STOP}}
      ]text right:#2}}}
\newcommand*\tikzRecursiveFunction[6][]{%
  % #1 = TikZ options
  % #2 = start
  % #3 = end
  % #4 = return bottom
  % #5 = return others
  % #6 = function
\begin{tikzpicture}[
  thick, >={Latex},
  start chain=going above, node distance=5mm,
  every join/.append style=<-,
  function/.style={
    shape=rectangle, draw, minimum width=3cm, rounded corners},
  return path/.style={out=5, in=-5, ->, min distance=10mm},
  label row/.code={\tikzLabelRow##1,\STOP},
  return node/.style args={##1,##2}{
    label row={##2}, node contents={\textbf{return} ##1}},
  return node'/.style={
    node contents={\textbf{return}~\null},
    label={[anchor=text, name=\tikzchaincurrent-right]text right:{##1}}},
  return conn/.style={gray, ->},
  function #3/.style={draw=none, overlay, node contents=\vphantom{()}}]
\def\tikzRecFrom{\tikzchaincurrent-left}
\def\tikzRecTo{\tikzchaincurrent-right}
\foreach \tikzRecItem in {#2, ..., #3}
  \node[
    function, node contents={#6(\tikzRecItem)}, function \tikzRecItem/.try,
    on chain, join,
    join=by {return path,
      /utils/TeX/ifnum={\tikzRecItem=\pgfinteval{#2+1}}
        {edge node={node[right, return node'=#4]}}
        {edge node={node[right, return node={#5}]}}},
    /utils/TeX/ifnum={\tikzRecItem>\pgfinteval{#2+1}}{
      join=by {return conn, to path={(\tikzchainprevious-right) -- (\tikzchaincurrent-left)}}}
  ];
\end{tikzpicture}}
\begin{document}
\tikzRecursiveFunction
  {0}{5}
  {1}{               $\inteval{\tikzRecItem-1} \cdot {}$,
      (\tikzRecFrom) \calcFactorial{\tikzRecItem-2},
                     ${}={}$,
      (\tikzRecTo)   \calcFactorial{\tikzRecItem-1}}{factorial}

\tikzRecursiveFunction
  {1}{13}
  {1}{               $\inteval{\tikzRecItem-1} \cdot {}$,
      (\tikzRecFrom) \calcFactorial{\tikzRecItem-2},
                     ${}={}$,
      (\tikzRecTo)   \calcFactorial{\tikzRecItem-1}}{factorial}

\tikzRecursiveFunction
  {0}{10}
  {0}{              $\inteval{\tikzRecItem-1} + {}$,
     (\tikzRecFrom) \inteval{(\tikzRecItem-1)*(\tikzRecItem-2)/2},
                    ${}={}$,
     (\tikzRecTo)   \inteval{\tikzRecItem*(\tikzRecItem-1)/2}}
     {sum}
\end{document}

Output

enter image description here enter image description here enter image description here

6
  • 4
    I'll admit, it wasn't as easy as I've expected it to be. Dec 23, 2022 at 22:40
  • This is beautiful! Like you said, though, it definitely looks challenging and is something I certainly wouldn't have come up with :-) Thanks for the answer. Dec 23, 2022 at 23:13
  • 1
    Worthy of the TikZ manual itself ;)
    – Pier Paolo
    Dec 24, 2022 at 0:23
  • Excellent ! Nice tour description.
    – MS-SPO
    Dec 24, 2022 at 12:51
  • 1
    @MS-SPO Thanks. I'm sure, I've lost a few people on the last leg of the tour, though. Sometimes, it isn't easy explaining my though process. Dec 24, 2022 at 14:10

You must log in to answer this question.

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