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

根据MSDN文档，在编写递归函数时，使用累加器参数会使函数尾递归，从而节省堆栈空间。我使用MSDN网站给出了两个例子在列表 -为什么tail递归函数对于正常递归函数成功执行的输入失败？

第一无尾计算所有数字的总和recursion-

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

现在用尾巴recursion-

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

并使用输入[1..100000]运行这两个函数。函数Sum成功地计算了此列表的总数，但给出了stackoverflow例外，如果我通过[1..1000000] ，但第二个函数Sumtail未能在[1..100000]，同时它应该提供更好的性能，因为它使用尾递归的第一个函数。是否还有其他影响递归函数的因素？

来源

2012-04-11 Kapil

我相信你误解了某些东西 - 使用累加器参数不会产生函数尾递归。累加器参数是一种用于在使用尾递归函数时累加值的技术。这是一种通常会产生尾递归的技术，但它没有定义尾递归。 – 2012-04-11 13:30:01

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

将loop t acc + h更改为loop t (acc + h)以使函数变成尾递归。

来源

2012-04-11 12:26:03 pad

那是正确的，但我不能标记它正确答案（仍然是6分钟）。这是什么差异？ – Kapil 2012-04-11 12:28:54

必须将'+'运算符应用于循环中的返回值，因此编译器不能使用尾递归，这会忘记每次递归调用的h状态。如果可以忘记状态 - 如果我们知道返回值将通过所有未修改的堆栈帧返回，则尾递归将起作用。 – 2012-04-11 12:37:00

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

回答

相关问题