为什么对于正常递归函数成功执行的输入,尾递归函数失败？

Question

根据MSDN文档,在编写递归函数时,使用accumulator参数使函数tail递归,从而节省了堆栈空间.我在MSDN网站上使用了两个例子来计算列表中所有数字的总和 -

首先没有尾递归 -

let rec Sum myList =
    match myList with
    | [] -> 0
    | h::t -> h + Sum t

现在有尾递归 -

let Sumtail list =
    let rec loop list acc =
        match list with
        | h::t -> loop t acc + h
        | [] -> acc
    loop list 0

并使用输入运行这两个函数[1..100000].函数Sum成功计算了此列表的总和,但是如果我通过[1..1000000] 但是第二个函数Sumtail 失败,则会给出stackoverflow异常,[1..100000]而它应该提供比第一个函数更好的性能,因为它使用尾递归.还有其他因素会影响递归函数吗？

Answer 1

你的第二个功能是不是尾递归,因为loop t acc + h作为被解析(loop t acc) + h这使得+成为最后的操作loop.

更改loop t acc + h为loop t (acc + h)函数变为尾递归.