递归拆卸字符串时，避免stackoverflow

Question

我正在为代码2018（剧透警告）的到来问题解决方案，其中我需要一个函数，该函数接受一个字符串（或一个char list），并在它们反应时删除每对字符。本练习描述了两个字符或“聚合物”中的“元素”，当它们是相同字母但大小写不同时会发生反应。所以从开始AbBc会离开你Ac。请记住，在一个反应​​之后，两个字符可能会彼此并排出现，而不是在以前，并引起新的反应。

我以为我可以通过使用仅处理前两个字符并递归调用自身的递归函数来解决此问题，但是由于输入字符串很大，因此会导致stackoverflow 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因为它“累加”了值。而是加入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