recursion - 尾递归与前向递归

Question

有人能给我这两种递归和示例之间的区别(特别是在 OCaml 中)吗？

Answer 1

尾递归函数是一种函数，其中唯一的递归调用是函数中的最后一个。非尾递归函数是不是这种情况的函数。

向后递归是一种递归，其中每次递归调用中参数的值都小于上一步中的参数值。前向递归是一种每一步都变得越来越大的递归。

这是两个正交的概念，即前向递归可能是也可能不是尾递归，这同样适用于后向递归。

例如，阶乘函数在命令式语言中通常是这样编写的:

fac = 1
for i from 1 to n:
    fac := fac * i

阶乘的常见递归版本向后计数(即，它以 n-1 作为参数调用自身)，但是如果您直接翻译上述命令式解决方案，您会想出向上计数的递归版本。它看起来像这样:

let fac n =
  let rec loop i =
    if i >= n
    then i
    else i * loop (i+1)
  in
    loop 1

这是一个前向递归，正如您所看到的，它比后向递归变体稍微麻烦一些，因为它需要一个辅助函数。现在这不是尾递归，因为循环中的最后一个调用是乘法，而不是递归。因此，要使其成为尾递归，您需要执行以下操作:

let fac n =
  let rec loop acc i =
    if i >= n
    then acc
    else loop (i*acc) (i+1)
  in
    loop 1 1

现在这既是前向递归又是尾递归，因为递归调用是 a) 尾调用和 b) 使用更大的值 (i+1) 调用自身。