不带返回值、堆栈或数组的多个递归(仅全局变量)



这个问题是关于一种名为"Liquid"的高级模板语言的。我为什么标记它为程序集?因为我认为汇编程序员在手动处理多次递归方面有更多的经验。

在液体中,您可以通过包含具有特定参数的文件来创建"函数":

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

到目前为止,一切都很好——如果我们有返回的方法,我们可以用它创建一个有效的多重递归循环。

不幸的是,液体是我见过的最难理解的逻辑形式之一。它几乎还没有完成。没有返回值,没有作用域,数组只是可以拆分的字符串。

在我编写的多重递归函数中,全局变量会被子调用所破坏。我在这里连一堆都没有!

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

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

  • 将它们填充到全局变量中,并在调用子节点之前隐藏变量
    • 哦,不!藏匿的东西也会被砸碎
  • 我一直在努力寻找其他一些神秘的逻辑,但却找不到

我想要神秘的逻辑!

利用活跃总是向上传播的事实,应该有一些操作顺序可以正确地完成它,但我已经为此头疼了3天,我很难理清思路。

以下是有问题的代码,但阅读可能会使其更加混乱。

编译器(和asm程序员)通过在堆栈上推送状态、进行调用,然后从堆栈中弹出状态来实现多重递归。所以局部变量和参数都在堆栈中。

只要有足够的堆栈空间用于最大调用深度,这就可以递归地工作。

我认为要使递归工作(当然不是尾递归),你需要实现某种可以用作堆栈的数据结构,将状态推到它上面,然后将它弹出

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

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


不过,您可能能够用一个实际上不是递归的函数来实现您的特定算法。你说过要穿过一棵树吗?也许可以参阅使用常量空间和O(n)运行时编写二进制搜索树的非递归遍历。其中一些涉及修改树。当然,如果你的树节点有父指针,遍历就很容易了,因为你可以在从一侧往下走后找到返回的路。

在我的递归包含中,我做这个

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

此处的实例

最新更新