尾递归与前向递归

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

这是一个前向递归,你可以看到它比后向递归变量稍微麻烦,因为它需要一个辅助函数.现在这不是尾递归,因为最后一次调用loop是乘法,而不是递归.所以为了使它具有尾递归性,你可以这样做:

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).

Answer 2

这是一个尾递归因子函数的例子:

let fac n =
let rec f n a =
    match n with
    0 -> a
    | _ -> f (n-1) (n*a)
in
f n 1

这是它的非尾递归对应物:

let rec non_tail_fac n =
match n with
0 -> 1
| _ -> (non_tail_fac n-1) * n

尾递归函数使用累加器a来存储前一个调用的结果值.这允许OCaml执行尾调用优化,这导致堆栈不溢出.通常,尾递归函数将使用累加器值以允许发生尾调用优化.