为什么这不是尾递归？

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

Answer 1

sum2 b a + accum

请注意,这被解析为(sum2 b a) + accum,而不是sum2 b (a + accum).

所以这个叫sum2 b a.然后它接受该调用的结果并添加accum到它.所以评估的最后一个表达式是加法,而不是调用sum2.因此,呼叫sum2不是尾部呼叫.

Answer 2

也许编译器在阅读

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

代替

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