递归拆解字符串时避免stackoverflow

Question

我正在为 advent of code 2018（剧透警报）的一个问题寻找解决方案，我需要一个接受字符串（或 char list) 并在它们反应时删除每对字符。该练习描述了两个字符，或 "polymer" 中的 "elements"，当它们是相同的字母但只是大小写不同时做出反应；所以从 AbBc 开始会让你得到 Ac。请记住，在一个反应之后，两个字符可能会彼此相邻，而它们之前没有，并引起新的反应。

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

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 因为它 "accumulates" 值。我们没有将 left 添加到递归调用的 return 值，而是将其添加到累加器并将其传递。然后当我们耗尽输入时，我们 return 累加器而不是空列表。

我还冒昧地附加了 [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

递归拆解字符串时避免stackoverflow

Avoid stackoverflow when recursively dismantling a string

stack-overflow

recursion

f#

tail-recursion