f# - 为什么即使使用连续传递风格，遍历大型二叉树也会导致堆栈溢出？

Question

本书的第 9 章 Expert F# 3.0 展示了如何在遍历二叉树时使用连续传递样式来避免堆栈溢出。我编写的树遍历代码与书中的代码几乎相同，但仍然出现堆栈溢出。我的代码如下:

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

不幸的是，这可能无法帮助您实际解决问题，但也许它提供了一些查找位置的指示。首先，代码和设置。我减小了树本身的大小以使其能够在 Windows 上运行。其余的是.NET 4.6，64位，win7，在VS2015 Update3。

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

这是用尾调用编译的，在Release模式下优化:

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

现在让我们在 Debug模式下编译它:

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

而且，哎呀:

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

那么有什么区别呢？

在发布版本中，如果反编译 IL，则有 9 个 tail 调用，我认为这是由某种 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)

在调试版本中，这将丢失:

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因为它同时具有算法的递归和尾递归版本。