爲什麼遍歷一個較大的二叉樹會導致堆棧溢出，即使使用continuation-passing樣式？

Question

本書的第9章Expert F＃3.0顯示瞭如何在遍歷二叉樹時避免堆棧溢出時使用continuation-passing樣式。我編寫了與本書代碼幾乎相同的樹遍歷代碼，但是我仍然遇到堆棧溢出問題。我的代碼如下：

type 'a Tree = 
    | Leaf of 'a 
    | Branch of 'a Tree * 'a Tree 

let rec mkLeftLeaningTree n tree = 
    if n = 0 then 
    tree 
    else 
    Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right") 

let leftLeaningTree1 = Leaf "left" 
let leftLeaningTree2 = mkLeftLeaningTree 30000 leftLeaningTree1 
let leftLeaningTree3 = mkLeftLeaningTree 30000 leftLeaningTree2 
let leftLeaningTree4 = mkLeftLeaningTree 30000 leftLeaningTree3 
let leftLeaningTree5 = mkLeftLeaningTree 30000 leftLeaningTree4 
let leftLeaningTree6 = mkLeftLeaningTree 30000 leftLeaningTree5 

let sizeContAcc tree = 
    let rec worker acc tree cont = 
    match tree with 
     | Leaf _    -> cont (acc + 1) 
     | Branch (left, right) -> worker acc left (fun acc -> 
           worker acc right cont) 
    worker 0 tree id 

裝載到F＃交互式環境這一點，並計算表達式sizeContAcc leftLeaningTree6使堆棧溢出。爲什麼是這樣？

Answer 1

我的第一個猜測是你在你的cont參數中將函數堆疊在一起，我把它理解爲可能會溢出的堆棧（雖然它是一個堆棧，正如Wolfgang在註釋中解釋的那樣）但我做了一些使用cont參數進行測試，並且不會導致任何計算器溢出。相反，我有一個顯着的放緩，最終達到了內存溢出。

一個解決您的具體問題將很明確地存儲，你需要在列表中探索（你仍然會受到的最大大小列表限制）樹木：

let sizeContAcc tree = 
    let rec worker acc tree contList = 
    match tree with 
     | Leaf _ -> 
     match contList with 
     | [] -> acc+1 
     | t::cl -> worker (acc+1) t cl 
     | Branch (left, right) -> worker acc left (right::contList) 
    worker 0 tree [] 

它作品，立即給我150001 leftLeaningTree6。

Answer 2

不幸的是，這可能不會幫助您真正解決問題，但它可能提供了一些指向哪裏看。首先，代碼和設置。我自己減小了樹的大小，使它在Windows上工作。其餘的是VS2015 Update3中的.NET 4.6,64位win7。

type 'a Tree = 
    | Leaf of 'a 
    | Branch of 'a Tree * 'a Tree 

[<EntryPoint>] 
let main argv = 

    ///https://stackoverflow.com/questions/40477122/why-does-traversing-a-large-binary-tree-result-in-a-stack-overflow-even-when-usi 



    let rec mkLeftLeaningTree n tree = 
     if n = 0 then 
     tree 
     else 
     Branch (mkLeftLeaningTree (n - 1) tree, Leaf "right") 



    let leftLeaningTree1 = Leaf "left" 
    let leftLeaningTree2 = mkLeftLeaningTree 15000 leftLeaningTree1 
    let leftLeaningTree3 = mkLeftLeaningTree 15000 leftLeaningTree2 
    let leftLeaningTree4 = mkLeftLeaningTree 15000 leftLeaningTree3 
    let leftLeaningTree5 = mkLeftLeaningTree 15000 leftLeaningTree4 
    let leftLeaningTree6 = mkLeftLeaningTree 15000 leftLeaningTree5 
    let leftLeaningTree7 = mkLeftLeaningTree 15000 leftLeaningTree6 
    let leftLeaningTree8 = mkLeftLeaningTree 15000 leftLeaningTree7 
    let leftLeaningTree9 = mkLeftLeaningTree 15000 leftLeaningTree8 
    let leftLeaningTree10 = mkLeftLeaningTree 15000 leftLeaningTree9 
    let leftLeaningTree11 = mkLeftLeaningTree 15000 leftLeaningTree10 
    let leftLeaningTree12 = mkLeftLeaningTree 15000 leftLeaningTree11 
    let leftLeaningTree13 = mkLeftLeaningTree 15000 leftLeaningTree12 
    let leftLeaningTree14 = mkLeftLeaningTree 15000 leftLeaningTree13 
    let leftLeaningTree15 = mkLeftLeaningTree 15000 leftLeaningTree14 
    let leftLeaningTree16 = mkLeftLeaningTree 15000 leftLeaningTree15 
    let leftLeaningTree17 = mkLeftLeaningTree 15000 leftLeaningTree16 
    let leftLeaningTree18 = mkLeftLeaningTree 15000 leftLeaningTree17 
    let leftLeaningTree19 = mkLeftLeaningTree 15000 leftLeaningTree18 
    let leftLeaningTree20 = mkLeftLeaningTree 15000 leftLeaningTree19 
    let leftLeaningTree21 = mkLeftLeaningTree 15000 leftLeaningTree20 
    let leftLeaningTree22 = mkLeftLeaningTree 15000 leftLeaningTree21 
    let leftLeaningTree23 = mkLeftLeaningTree 15000 leftLeaningTree22 
    let leftLeaningTree24 = mkLeftLeaningTree 15000 leftLeaningTree23 
    let leftLeaningTree25 = mkLeftLeaningTree 15000 leftLeaningTree24 
    let leftLeaningTree26 = mkLeftLeaningTree 15000 leftLeaningTree25 
    let leftLeaningTree27 = mkLeftLeaningTree 15000 leftLeaningTree26 
    let leftLeaningTree28 = mkLeftLeaningTree 15000 leftLeaningTree27 
    let leftLeaningTree29 = mkLeftLeaningTree 15000 leftLeaningTree28 
    let leftLeaningTree30 = mkLeftLeaningTree 15000 leftLeaningTree29 
    let leftLeaningTree31 = mkLeftLeaningTree 15000 leftLeaningTree30 

    let sizeContAcc tree = 
     let rec worker acc tree cont = 
     match tree with 
      | Leaf _    -> cont (acc + 1) 
      | Branch (left, right) -> worker acc left (fun acc -> 
            worker acc right cont) 
     worker 0 tree id 



    sizeContAcc leftLeaningTree31 |> printfn "%A" 

    printfn "%A" argv 
    0 // return an integer exit code 

這是編譯尾調用，優化發行方式：

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Release\ConsoleApplication8.exe --debug:pdbonly --noframework --define:TRACE --doc:bin\Release\ConsoleApplication8.XML --optimize+ --platform:x64 -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Release\ConsoleApplication8.exe

因此，與31種樹木這個工程：

.\ConsoleApplication8.exe 
450001 

現在讓我們編譯這個在調試模式：

C:\Program Files (x86)\Microsoft SDKs\F#\4.0\Framework\v4.0\fsc.exe -o:obj\Debug\ConsoleApplication8.exe -g --debug:full --noframework --define:DEBUG --define:TRACE --doc:bin\Debug\ConsoleApplication8.XML --optimize- --tailcalls- --platform:anycpu32bitpreferred -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\FSharp.NETFramework\v4.0\4.4.0.0\FSharp.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\mscorlib.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Core.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.dll" -r:"C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework.NETFramework\v4.6\System.Numerics.dll" --target:exe --warn:3 --warnaserror:76 --vserrors --LCID:1033 --utf8output --fullpaths --flaterrors --subsystemversion:6.00 --highentropyva+ --sqmsessionguid:057b9ccf-c89e-4da6-81ab-5295156e7a19 "C:\Users\userName\AppData\Local\Temp.NETFramework,Version=v4.6.AssemblyAttributes.fs" AssemblyInfo.fs Program.fs 1> ConsoleApplication8 -> C:\Users\userName\Documents\Visual Studio 2015\Projects\StackOverflow6\ConsoleApplication8\bin\Debug\ConsoleApplication8.exe

而且，oops：

> .\ConsoleApplication8.exe 
Process is terminated due to StackOverflowException. 

那麼有什麼區別？

在發佈版本中有9 tail調用，如果你反編譯IL，並且我認爲這是由某種while循環表示的。

IL_0073: ldloc.s 6 
IL_0075: tail. 
IL_0077: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0) 

在Debug版本，這將是丟失：

L_007d: ldloc.s 6 
IL_007f: call int32 [FSharp.Core]Microsoft.FSharp.Core.LanguagePrimitives/HashCompare::GenericComparisonWithComparerIntrinsic<!a>(class [mscorlib]System.Collections.IComparer, !!0, !!0) 
IL_0084: ret 

對於一個簡單的例子來測試您可以檢查此Question因爲它的算法都遞歸和尾遞歸版本。