如何使递归函数“跟踪”？

Question

与任何 TikZ 图片一样……只需从某个地方开始并构建它。

对于你的照片，我选择chains图书馆这不是创建仅包含节点和边的图表的最先进的技术 - 该graphs库就是为此而制作的，并且具有高级输入语法 - 但它非常接近普通的 TikZ 并且非常容易适应。

它的主要两个功能是

根据一个规则放置多个节点，并
“连接”这些节点（即在它们之间画边）。

positioning只需使用库（它本身只是为节点的相对定位提供了一些小的快捷方式）和edge操作（它本身已经相当强大）就可以完成其中的任何操作。

但我们不必担心边缘情况（第一个节点不能与前一个节点连接，也不能相对于另一个节点放置）。

仅凭这张小小的 TikZ 图片

% 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}

你已经得到了

已经完成一半了！

现在，我们可以添加另一个循环来绘制这样的弯曲路径：

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

由于我没有给该链命名（在之前没有任何内容going），因此它被命名并且其节点可以通过、等chain访问。第一个和最后一个可以分别通过名称和访问。chain-1chain-2chain-beginchain-end

但这只是另一个连接！
由于最后一个箭头很难处理，我将在其位置放置一个相同大小的隐形节点。

为了更概括这一点，我将添加一个宏来指定节点总数 (+ 1)。为了实现不可见节点，我将使用来node contents定义节点的内容，而不是{…}允许我用另一个文本覆盖节点内容的语法。

我们将添加另一个连接并...

\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}

我们将添加overlay到function \tikzMaxRecursion键，以便图片顶部不会有额外的空白。

让我们添加带有返回箭头的节点。
由于第一个节点会有所不同，因此我使用ext.misc图书馆我的tikz-ext包裹将第一个连接放置在不同的边缘节点上。

只需添加少量

\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}}}
    }];

我们得到

此时，我们实际上必须考虑该图的递归元素或其显示的值。

对于这个简单的整数运算示例，在 TeX 中实现递归函数并让 TeX 实际完成所有工作要容易得多。
确实\foreach提供了一个选项remember来自上一次迭代的值，但这里似乎足够简单。（对于更复杂的函数，您可能最好在 TeX 之外生成值并直接输入它们。）

灰色箭头不太容易。我们要么手动调整起点和终点，要么让每个返回节点实际上都是多个节点。

还有这些edge node 是实际上每次有五个节点。使用特殊text right锚点 ([A]，[B]) 它们被放置在一个小行中，节点的文本部分之间没有空格——基本上是另一个链。这种方法效果最好，因为节点没有被转换。那么需要做更多的工作，也许tikzmark应该在这里使用库的子节点。

其中两个标签的名称从链中继承而来（\tikzchaincurrent返回链上当前节点的节点名称），我们可以在稍后绘制灰色箭头时引用它们。

我们现在可以在单独的循环中绘制这些灰色箭头：

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

但是我们也可以添加另一个连接，但不能针对链中的前两个主节点（因为我们还没有两个返回节点）。

为了使这个标签链可以与其他递归函数一起使用，我将介绍label row使用\tikzLabelRow解析器的关键。

基本上，您给出return node一个零件列表，如果零件以(<name>)该标签开头，则会分配名称<name>。

为了方便起见，宏的\tikzRecFrom设置\tikzRecTo方式使您不必考虑它们的实际名称。

我承认，它并不像我想象的那么简单——除了灰色箭头，我完全预料到它们会很麻烦。

不过，将坐标改为节点可以解决大多数令人烦恼的事情。

省略灰色箭头应该可以使其很容易地适应不同的递归函数。

代码

\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}

输出

Answer 1