为什么这不是尾递归？

Question

我正在阅读 实用函数式编程 这本书，尝试在阅读书中的例子之前想出自己的尾递归示例（参见列表 10.2，第 265 页）。书中的示例可以工作；我的示例会导致堆栈溢出。

我发现如果使用元组参数或预先计算 a + accum，则我的示例将起作用。我想了解原因。

let rnd = new System.Random()
let test2 = List.init 1000000 (fun _ -> rnd.Next(-50, 51))

let rec sum2 list accum =
  match list with
  | [] -> accum
  | a::b -> sum2 b a + accum

let result = sum2 test2 0

printfn "%d" result

- TrueWill

Answer 1

sum2 b a + accum

请注意，该表达式被解析为(sum2 b a) + accum，而不是sum2 b (a + accum)。

因此，这会调用sum2 b a。然后它将该调用的结果与accum相加。因此，最后计算的表达式是加法，而不是对sum2的调用。因此，对sum2的调用不是尾调用。

- sepp2k

Answer 2

也许编译器正在读取。

a::b -> (sum2 b a) + accum

替代

a::b -> sum2 b (a + accum)

- gpeche

---

啊！你和 @sepp2k 说得对。这是评估顺序的问题。括号可以解决它。 - TrueWill

我通常会过度使用括号，因为我发现这是比较好的选择。耶！Common Lisp！ - gpeche