如何停止递归？

Question

Advent of Code Day 1 需要以一种或另一种形式在一长串括号（如 ((((())(())(((()))(( 等）上循环。这个想法是 ( 上升一个 "floor" ,)下一层,目标是打印

字符串中楼层数为负数的第一个索引并且
找到字符串末尾时的最后一层。

带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 没有任何方法可以从递归调用中 "early return" 因为没有办法运行程序反向并且没有 concept of return -- 这没有任何意义。

我感觉递归可能不是 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)

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

祝你好运！

编辑： 关于你关于因子递归的问题，看看 the Ackermann Function in Factor and the Fibonacci sequence in Factor 你应该知道如何 "break the loop"。实际上唯一的问题在于思考（将自己从命令式模型中解放出来:)）；在函数式语言中没有 "return"，只有最终值，你提到的基于堆栈的语言是同一事物的其他计算模型（而不是考虑折叠树，而是考虑 "pushing and poping to/from the stacks" -顺便说一句，这是实现前者的常用方法。

编辑：（剧透！） 我安装了 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 ;

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

Answer 2

编辑

我最初误读了您计算 basement 值的方式。我已经更新了下面的答案

这是一个 JavaScript 解决方案。抱歉，我不知道这是如何转换为因子的。 reduce 是一个迭代过程

const worker = txt=>
  txt.split('').reduce(({floor, basement}, x, i)=> {
    if (x === '(')
      return {floor: floor + 1, basement}
    else if (basement === null && floor === 0)
      return {floor: floor - 1, basement: i}
    else
      return {floor: floor - 1, basement}
  }, {floor: 0, basement: null})
 
let {floor, basement} = worker('((((())(())(((()))((')
console.log(floor)    //=> 6
console.log(basement) //=> null; never reaches basement

上面的答案依赖于一些 .split 和 .reduce，它们可能不会以您的语言出现。这是另一个使用 Y-combinator 且仅内置 substring 的解决方案（大多数语言都包含）。这个答案还取决于您的语言是否具有 first-class 函数。

const U = f=> f (f)
const Y = U (h=> f=> f (x=> h (h) (f) (x)))

const strhead = s=> s.substring(0,1)
const strtail = s=> s.substring(1)

const worker = Y (f=> ({floor, basement})=> i=> txt=> {
  // txt is empty string; return answer
  if (txt === '')
    return {floor, basement}

  // first char in txt is '(', increment the floor
  else if (strhead (txt) === '(')
    return f ({floor: floor + 1, basement}) (i+1) (strtail (txt))

  // if basement isn't set and we're on floor 0, we found the basement
  else if (basement === null && floor === 0)
    return f ({floor: floor - 1, basement: i}) (i+1) (strtail (txt))

  // we're already in the basement, go down another floor
  else
    return f ({floor: floor - 1, basement}) (i+1) (strtail (txt))
}) ({floor: 0, basement: null}) (0)

{
  let {floor, basement} = worker('((((())(())(((()))((')
  console.log(floor)    //=> 6
  console.log(basement) //=> null; never reaches basement
}

{
  let {floor, basement} = worker(')(((((')
  console.log(floor)    //=> 4
  console.log(basement) //=> 0
}

{
  let {floor, basement} = worker('((())))')
  console.log(floor)    //=> -1
  console.log(basement) //=> 6
}

Answer 3

您可以使用 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

如何停止递归？

How to stop recursing?

recursion

functional-programming

declarative

factor-lang