没有 return 值、堆栈或数组的多重递归（仅限全局变量）

Question

这个问题是关于一种叫做 "Liquid" 的高级模板语言的。为什么我给它贴上了 assembly 的标签？因为我想汇编程序员在手动处理多重递归方面更有经验。

在 liquid 中，您可以通过包含具有特定参数的文件来创建 "Functions"：

{% include file var1="a" var2="b" %}

到目前为止一切顺利 - 如果我们有办法 return.

，我们可以用它创建一个有效的多重递归循环

不幸的是，液体是我见过的最无力的逻辑形式之一。它几乎没有图灵完备。没有 return 值，没有范围，数组只是可以拆分的字符串。

使用我正在编写的多重递归函数，全局变量会被子调用破坏。我什至没有可用的堆栈！

如果我在树节点上设置布尔值 true 并递归到较低节点，如果任何较低节点（或同一级别的后续节点）设置它，它将破坏较高节点的活动值。

这在一定程度上限制了我的选择：

将它们填充到全局变量中并在调用子节点之前存储变量
- 哦不！藏匿处也会被破坏！
我一直试图找到但找不到的其他一些神秘逻辑。

请给我神秘的逻辑！

利用 active 总是向上传播的事实，应该有一些操作顺序可以正确地完成它，但是我已经对这个问题进行了 3 天的抨击，而且我无法理清思路。

Here is the code in question 虽然阅读这可能会使这更混乱。

Answer 1

编译器（和 asm 程序员）通过将状态压入堆栈、进行调用、然后从堆栈中弹出状态来实现多重递归。所以局部变量和参数在栈上。

这会递归地工作，只要有足够的堆栈 space 来满足最大调用深度。

我认为要使递归工作（当然除了尾递归），您需要实现某种可以用作堆栈的数据结构，将状态推入其中并将其弹出。

完全通用的递归需要能够保存和恢复所需深度的状态。

如果您没有任何可变大小的存储，您可以实现一个小的固定大小的堆栈，其中包含全局变量，如 stack1、stack2、stack3 等，以及一个用作堆栈指针的计数器。您只需要与递归的最大深度一样多的变量。

不过，您也许可以使用实际上不是递归的函数来实现您的特定算法。你说了一些关于遍历树的事情？也许看到 Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time 的想法。其中一些涉及修改树。当然，如果你的树节点有父指针，那么遍历就很容易了，因为你可以从一边往下走，然后再往上走。

Answer 2

在我的递归包含中我这样做

{% assign n = include.n %}

{% if n == nil %}
  {% assign n = 0 %}
{% endif %}

++++ Do something on n
{% assign n = n  | plus: 1 %}

{% if n < something %}
  {% include self.html n=n %}
{% endif %}

++++ Reverse value of n to parent value
{% assign n = n  | minus: 1 %}

Live example here

没有 return 值、堆栈或数组的多重递归（仅限全局变量）

Multiple recursion without return values, a stack, or arrays (Only global variables)

recursion

assembly

liquid

jekyll