如何避免此F＃程序中的堆栈溢出（递归树搜索）？

Question

我有一个区分联合树是这样的：

type rbtree = 
    | LeafB of int 
    | LeafR of int 
    | Node of int*rbtree*rbtree 

而我所要做的就是寻找每个LeafB存在于树，所以我来到了这个递归函数：

let rec searchB (tree:rbtree) : rbtree list = 
    match tree with 
    | LeafB(n) -> LeafB(n)::searchB tree 
    | LeafR(n) -> [] 
    | Node(n,left,right) -> List.append (searchB left) (searchB right) 

但是，当我尝试测试它时，我得到堆栈溢出异常，我不知道如何修改它以正常工作。

Answer 1

由于@kvb表示您的更新版本不是真正的尾记录，并且可能会导致一个计算器。

你可以做的是基本上使用堆栈空间而不是堆栈空间。

let searchB_ tree = 
    let rec tail results continuation tree = 
    match tree with 
    | LeafB v   -> continuation (v::results) 
    | LeafR _   -> continuation results 
    | Node (_, lt, rt) -> tail results (fun leftResults -> tail leftResults continuation rt) lt 
    tail [] id tree |> List.rev 

如果我们ILSpy看生成的代码它本质上是这样的：

internal static a tail@13<a>(FSharpList<int> results, FSharpFunc<FSharpList<int>, a> continuation, Program.rbtree tree) 
{ 
    while (true) 
    { 
    Program.rbtree rbtree = tree; 
    if (rbtree is Program.rbtree.LeafR) 
    { 
     goto IL_34; 
    } 
    if (!(rbtree is Program.rbtree.Node)) 
    { 
     break; 
    } 
    Program.rbtree.Node node = (Program.rbtree.Node)tree; 
    Program.rbtree rt = node.item3; 
    FSharpList<int> arg_5E_0 = results; 
    FSharpFunc<FSharpList<int>, a> arg_5C_0 = new Program<a>.tail@17-1(continuation, rt); 
    tree = node.item2; 
    continuation = arg_5C_0; 
    results = arg_5E_0; 
    } 
    Program.rbtree.LeafB leafB = (Program.rbtree.LeafB)tree; 
    int v = leafB.item; 
    return continuation.Invoke(FSharpList<int>.Cons(v, results)); 
    IL_34: 
    return continuation.Invoke(results); 
} 

，以便与在F＃尾递归函数预计它tranformed成while循环。如果我们看一下非尾递归函数：

// Program 
public static FSharpList<int> searchB(Program.rbtree tree) 
{ 
    if (tree is Program.rbtree.LeafR) 
    { 
    return FSharpList<int>.Empty; 
    } 
    if (!(tree is Program.rbtree.Node)) 
    { 
    Program.rbtree.LeafB leafB = (Program.rbtree.LeafB)tree; 
    return FSharpList<int>.Cons(leafB.item, FSharpList<int>.Empty); 
    } 
    Program.rbtree.Node node = (Program.rbtree.Node)tree; 
    Program.rbtree right = node.item3; 
    Program.rbtree left = node.item2; 
    return Operators.op_Append<int>(Program.searchB(left), Program.searchB(right)); 
} 

我们看到的递归调用的函数Operators.op_Append<int>(Program.searchB(left), Program.searchB(right));

所以尾递归函数分配的，而不是创建一个新的堆栈帧延续功能结束。我们仍然可以用尽堆，但堆比堆多得多。

完整的示例展示了一个计算器：

type rbtree = 
    | LeafB of int 
    | LeafR of int 
    | Node of int*rbtree*rbtree 

let rec searchB tree = 
    match tree with 
    | LeafB(n) -> n::[] 
    | LeafR(n) -> [] 
    | Node(n,left,right) -> List.append (searchB left) (searchB right) 

let searchB_ tree = 
    let rec tail results continuation tree = 
    match tree with 
    | LeafB v   -> continuation (v::results) 
    | LeafR _   -> continuation results 
    | Node (_, lt, rt) -> tail results (fun leftResults -> tail leftResults continuation rt) lt 
    tail [] id tree |> List.rev 

let rec genTree n = 
    let rec loop i t = 
    if i > 0 then 
     loop (i - 1) (Node (i, t, LeafB i)) 
    else 
     t 
    loop n (LeafB n) 

[<EntryPoint>] 
let main argv = 
    printfn "generate left leaning tree..." 
    let tree = genTree 100000 
    printfn "tail rec" 
    let s  = searchB_ tree 
    printfn "rec" 
    let f  = searchB tree 

    printfn "Is equal? %A" (f = s) 

    0 

Answer 2

哦，我可能会带着一个解决方案：

let rec searchB (tree:rbtree) : rbtree list = 
match tree with 
| LeafB(n) -> LeafB(n)::[] 
| LeafR(n) -> [] 
| Node(n,left,right) -> List.append (searchB left) (searchB right) 

现在看起来正常工作，当我尝试它。