如何停止递归？

Question

代码的出现第1天需要以一种或那种形式循环一长串括号等((((())(())(((()))((.这个想法是(上升到一层,)下到一层,目标是打印

1. 字符串中第一个索引,其中楼层编号为负数
2. 找到字符串结尾时的最后一层.

使用for循环的命令式解决方案很简单(以Python为例):

def main():
    flr = 0
    basement = False
    for idx, elt in enumerate(text):
        flr += {
            "(": 1,
            ")": -1
        }.get(elt)

        if flr < 0 and not basement:
            print("first basement pos:", idx + 1)
            basement = True

    print("final floor:", flr)

递归函数解决方案稍微复杂一点,但仍然不太难.

def worker(flr, txt, idx, basement):
    flr += {"(": 1, ")": -1}[ txt[0] ]

    if not (len(txt) - 1): return flr

    if flr < 0 and not basement:
        print("first basement floor index: ", idx + 1)
        basement = True

    return worker(flr, txt[1:], idx + 1, basement)


def starter(txt):
    flr, basement, idx = 0, False, 0
    return worker(flr, txt, idx, basement)


if __name__ == '__main__':
    __import__("sys").setrecursionlimit(int(1e5))
    print("final floor:", starter(text))

这两个都给出了正确的输出

first basement floor index:  1795
final floor: 74

当我的挑战输入运行时.

_{除了第二个是愚蠢的,因为Python没有尾调用优化,但没关系}

如何在因子中实现这些中的任何一个？自从我开始使用Factor以来,这一直是我一直困惑的事情.

我们不能只使用for循环,因为没有等价物允许我们在迭代之间保持可变状态.

我们可以使用递归解决方案:

: day-1-starter ( string -- final-floor )
  [ 0 ] dip 0 f day-1-worker 3drop "final floor: %s" printf ;

: day-1-worker 
  ( floor string index basement? -- floor string index basement? )
  day-1-worker  ! what goes here?
  ; recursive

太好了,这是一个骨架,但身体里面是day-1-worker什么？Factor没有任何方法可以从递归调用中"提前返回",因为没有办法反向运行程序而没有返回的概念 - 这没有任何意义.

我觉得可能递归不是因子中这个问题的答案.如果是,我该如何停止递归？

Answer 1

首先，递归始终是答案:)因为这是一个挑战（而且我不知道因素），所以只是一个提示：在你的Python解决方案中，你已经使用了副作用来打印第一层地下室。完全没有必要！您也可以使用basemet参数来保存楼层号，如下所示：

    def worker(flr, txt, idx, basement):
        flr += {"(": 1, ")": -1}[ txt[0] ]

        if not (len(txt) - 1): return [flr, basement] # <- return both

        if flr < 0 and not basement:
            #print("first basement floor index: ", idx + 1) # side effects go away!
            basement = idx+1 # <- a number in not False, so that's all
        return worker(flr, txt[1:], idx + 1, basement)

所以现在你得到了

    final,first_basement = worker(0, txt, 0, False)

或者，您也可以编写两个函数，第一个函数查找地下一层的索引，另一个函数只计算最后一层。即使您确实关心性能，拥有 <2000 个额外的小步骤也没什么大不了的。

祝你好运！

编辑：关于因子中的递归问题，请查看因子中的阿克曼函数和因子中的斐波那契数列，您应该了解如何“打破循环”。其实唯一的问题在于思维（把自己从命令式的模式中解放出来:)）；在函数式语言中，没有“返回”，只有最终值，而您提到的基于堆栈的语言是同一事物的其他计算模型（而不是考虑折叠一棵树，而是考虑“推入堆栈或从堆栈弹出”） “——顺便说一句，这是实现前者的常见方法）。

编辑：（剧透！） 我安装了 Factor 并开始使用它（非常好），对于第一个问题（计算最终分数），一个可能的解决方案是

    : day-1-worker (  string floor -- floor )
      dup length 0 = 
       [ drop ]
       [ dup first 40 =
         [ swap 1 + ]
         [ swap 1 - ]
         if
         swap rest
         day-1-worker ]
       if ;

    : day-1-starter ( string -- floor )
      0 swap day-1-worker ;

所以现在你可以编写类似的一个来计算地下室的索引，或者（这会更酷！）修改它，以便它也管理索引和地下室......（可能使用cond比嵌套if更明智）。