代码之家 › 专栏 › 技术社区 › Mau

这个序列表达式应该是尾部递归的吗?

tail-recursion stack-overflow f#

Mau · 技术社区 · 14 年前

这个f seq表达式在我看来是尾部递归的,但我得到了堆栈溢出异常(启用了尾部调用)。有人知道我错过了什么吗?

let buildSecondLevelExpressions expressions =
    let initialState = vector expressions |> randomize
    let rec allSeq state = seq {
        for partial in state do
            if count partial = 1
            then yield Seq.head partial
            if count partial > 1 || (count partial = 1 && depth (Seq.head partial) <= MAX_DEPTH) then
                let allUns = partial
                                |> pick false 1
                                |> Seq.collect (fun (el, rr) -> (createExpUnaries el |> Seq.map (fun bn -> add rr bn)))
                let allBins = partial  // Careful: this case alone produces result recursivley only if |numbers| is even (rightly!).
                                |> pick false 2
                                |> Seq.collect (fun (el, rr) -> (createExpBinaries el |> Seq.map (fun bn -> add rr bn)))
                yield! allSeq (interleave allBins allUns)
    }
    allSeq initialState

如果你想知道,尽管这不重要, pick 用于在序列和 interleave 交错2个序列中的元素。 vector 是的构造函数 ResizeArray .

3 回复 | 直到 9 年前

Tomas Petricek 14 年前

正如Gideon所指出的,这不是尾部递归,因为“状态”列表中还有其他元素要处理。使这个尾部递归并不简单,因为您需要一些队列应处理的元素。

下面的伪代码显示了一种可能的解决方案。我补充说 work 存储要完成的剩余工作的参数。每次调用时,我们只处理第一个元素。所有其他元素都将添加到队列中。完成后,我们从队列中选择更多的工作:

let rec allSeq state work = seq { 
    match state with 
    | partial::rest -> 
        // Yield single thing to the result - this is fine
        if count partial = 1 then yield Seq.head partial 
        // Check if we need to make more recursive calls...
        if count partial > 1 || (* ... *) then 
            let allUns, allBins = // ...
            // Tail-recursive call to process the current state. We add 'rest' to 
            // the collected work to be done after the current state is processed
            yield! allSeq (interleave allBins allUns) (rest :: work)
        else
            // No more processing for current state - let's take remaining
            // work from the 'work' list and run it (tail-recursively)
            match work with 
            | state::rest -> yield! allSeq state rest
            | [] -> () //completed
    | _ -> 
        // This is the same thing as in the 'else' clause above. 
        // You could use clever pattern matching to handle both cases at once
        match work with 
        | state::rest -> yield! allSeq state rest
        | [] -> () } //completed

J D 14 年前

我找不到序列表达式中调用位于f尾部位置的定义,因此强烈建议不要编写依赖于当前实现语义的代码,即这是未定义的行为。

例如,尝试枚举(例如应用 Seq.length )以下序列导致堆栈溢出:

let rec xs() = seq { yield! xs() }

但是,正如托马斯指出的那样,以下事实确实有效:

let rec xs n = seq { yield n; yield! xs(n+1) }

我的建议是总是用 Seq.unfold 相反。在这种情况下,您可能希望积累要完成的工作(例如,当您递归到左分支时,您将右分支推到收集器中的堆栈上)。

FWIW,甚至 the F# language reference 弄错了。它提供了以下用于展平树的代码:

type Tree<'a> =
   | Tree of 'a * Tree<'a> * Tree<'a>
   | Leaf of 'a

let rec inorder tree =
    seq {
      match tree with
          | Tree(x, left, right) ->
               yield! inorder left
               yield x
               yield! inorder right
          | Leaf x -> yield x
    }

他们自己的代码杀死了F Interactive,当向左边的一棵深树进纸时,堆栈溢出。

Gideon Engelberth 14 年前

这不会是尾部递归,因为您可以多次递归调用。要转换为伪代码:

allSeq(state)
{
    foreach (partial in state)
    {
        if (...)
        {
            yield ...
        }
        if (...)
        {
            ...
            //this could be reached multiple times
            yield! allSeq(...)
        }
    }
}