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

Question

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

我想我可以通过使用只处理前两个字符并递归调用自身的递归函数来解决这个问题，但是由于输入字符串非常大，这会导致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#，所以欢迎任何指点。任何人都可以以实用的方式解决这个问题吗？

标签： recursionf#stack-overflowtail-recursion

Answer 1

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

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

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

我还冒昧地附加了, [left] @ ..., 作为一个缺点,left::...因为后者比前者更有效。我也移动了left,right和rest模式，因为这样更整洁、更安全。您通常应该避免使用List.headandList.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