f# - 这个序列表达式应该是尾递归的吗？

Question

这个 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 的构造函数。

Answer 1

正如 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