recursion - 如何停止递归？

Question

Advent of Code Day 1需要以一种或另一种形式循环在一长串括号上，如 ((((())(())(((()))((等等。这个想法是(上一层“楼”，)下降一层，目标是打印

楼层数为负的字符串中的第一个索引和

找到字符串末尾时的最后一层。

使用 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 中实现其中任何一个？自从我开始使用 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 的 body 里有什么东西? Factor 无法从递归调用中“提前返回”，因为无法反向运行程序，也没有返回的概念——这没有任何意义。

我觉得也许递归不是 Factor 中这个问题的答案。如果是，我该如何停止递归？

Answer 1

您可以使用 cum-sum 组合器:

: to-ups/downs ( str -- seq )
    [ CHAR: ( = 1 -1 ? ] { } map-as ;

: run-elevator ( str -- first-basement final-floor )
    to-ups/downs cum-sum [ -1 swap index 1 + ] [ last ] bi ;

IN: scratchpad "((())))(())(())(((()))((" run-elevator

--- Data stack:
7
2