recursion - 递归拆解字符串时避免stackoverflow

Question

我正在为 advent of code 2018 的问题寻找解决方案(剧透警报)我需要一个函数，它接受一个字符串(或一个字符列表)并在它们 react 时删除每对字符。该练习描述了“聚合物”中的两个字符或“元素”，当它们是相同的字母但只是大小写不同时会发生 react ；所以从 AbBc 开始，你会得到 Ac。请记住，在一个 react ​​之后，两个字符可能会彼此相邻，而它们之前没有，并引起新的 react 。

我想我可以通过使用只处理前两个字符并递归调用自身的递归函数来解决这个问题，但是由于输入字符串非常大，这会导致 stackoverflow 异常:

let rec react polymer =
    match polymer with
    | [] -> []
    | [x] -> [x]
    | head::tail ->
        let left = head
        let right = List.head tail
        let rest =  List.tail tail
        // 'reacts' takes two chars and
        // returns 'true' when they react
        match reacts left right with
        // when reacts we go further with
        // the rest as these two chars are
        // obliterated
        | true -> react rest
        // no reaction means the left char
        // remains intact and the right one 
        // could react with the first char 
        // of the rest
        | false -> [left] @ react tail

然后，我只是试图解决练习以获得针对单元测试的正确答案，我尝试强制执行此操作，但很快就变得一团糟，现在我有点卡住了。我正在自学 f# 所以欢迎任何指点。谁能以功能的方式解决这个问题？

Answer 1

您可以通过重写您的函数以使用尾递归来避免堆栈溢出，这只是意味着递归调用应该是最后执行的操作。

当你执行 [left] @react tail 时，你首先进行递归调用，然后将 [left] 附加到该结果。这意味着它必须在执行递归调用时保持当前函数上下文(称为堆栈帧)，如果递归调用以及堆栈帧加起来，直到出现堆栈溢出。但是，如果在当前函数上下文中没有更多工作要做，则可以释放(或重用)堆栈帧，因此不会出现堆栈溢出。

您可以通过添加另一个函数参数使其尾部递归，通常称为 acc 因为它“累积”值。我们没有将 left 添加到递归调用的返回值，而是将其添加到累加器并将其传递。然后当我们耗尽输入时，我们返回累加器而不是空列表。

我还冒昧地将附加 [left] @ ... 作为缺点，left::...，因为后者效率比前者高很多。我还将 left、right 和 rest 移到了该模式中，因为这样更简洁、更安全。您通常应该避免使用 List.head 和 List.tail，因为它们在空列表上会失败并且是等着发生的错误。

let rec react acc polymer =
    match polymer with
    | [] -> acc
    | [x] -> x::acc
    | left::right::rest ->
        match reacts left right with
        | true -> react acc rest
        | false -> react (left::acc) (right::rest)

你也可以使用守卫而不是嵌套的 matches(无论如何它实际上应该是一个 if):

let rec react acc polymer =
    match polymer with
    | [] ->
        acc
    | [x] ->
        x::acc
    | left::right::rest when reacts left right ->
        react acc rest
    | left::rest ->
        react (left::acc) rest