如何避免此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) 

現在看起來正常工作，當我嘗試它。