向一个可变列表追加时的堆栈溢出

Question

我想写一个递归函数，该函数适用于具有可变列表字段的记录类型。

这个函数应该在递归调用期间修改可变字段，向列表中添加新的值。一切都很好，但当输入数据量开始增加时，我开始得到堆栈溢出错误。

下面是一个最小的例子，展示了我的问题。

type ty = { mutable ll : int list; }

let build_list i n =
  let rec aux acc i =
    if i <= n then
      aux (i::acc) (i+1)
    else (List.rev acc)
  in
  aux [] i

let rec mod_rec (acc: int) (a: ty) : (int) =
    a.ll <- a.ll @ (build_list 0 4000);
    let acc = if acc > 0 then mod_rec (acc - 1) a else 0 in
    acc

let aty = { ll = [] } in
mod_rec 1000 aty

这导致了下面的错误

Stack overflow during evaluation (looping recursion?).
Raised by primitive operation at file "stdlib.ml", line 296, characters 22-31
Called from file "stdlib.ml", line 296, characters 22-31

当使用尾部递归函数时，我也得到了同样的错误。

我不太明白这是怎么回事。编译器在栈上分配了什么值？为什么它不使用堆来存储列表元素？

解决这个问题的最佳实践是什么？我应该选择其他数据结构还是使用具有破坏性更新的不可变列表？

谢谢你的建议。

Answer 1

我认为问题在于 @ 运算符 List.append)不是尾部递归。

文件中这样说。

连接两个列表。与导数运算符@相同。不是尾递归（第一个参数的长度）。

你可以通过写一个尾递归的追加函数来解决这个问题。