为什么即使使用延续传递样式,遍历大型二叉树也会导致堆栈溢出？

Question

专家F#3.0一书的第9章介绍了如何在遍历二叉树时使用延续传递样式来避免堆栈溢出.我编写的树遍历代码几乎与本书中的代码完全相同,但我仍然得到了堆栈溢出.我的代码如下:

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 []

它有效并立即为我提供了 leftLeaningTree6 的 150001 。