尾递归 vs. 前向递归

Question

能否有人给我解释一下这两种递归的区别和示例（特别是在OCaml中）？

- REALFREE

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) 调用自身。

- sepp2k

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执行尾调用优化，从而避免栈溢出。通常，尾递归函数会利用累加器的值来实现尾调用优化。

- sashang

---

除非我误解了前递归的含义（我承认我之前从未听说过这个术语，不得不在谷歌上搜索），否则你的两个函数都不是前递归的。 - sepp2k

看起来我错过了问题中的“正向”递归部分。 - sashang

Answer 3

例如，一个递归函数build_word，它接受一个char list并将它们组合成一个字符串，即['f'; 'o'; 'o']变为字符串"foo"。归纳过程可以这样可视化：

build_word ['f'; 'o'; 'o']
"f" ^ (build_word ['o'; 'o'])
"f" ^ ("o" ^ (build_word ['o'])    // base case! return "o" and fold back
"f" ^ ("o" ^ ("o"))
"f" ^ ("oo")
"foo"

这是一个普通的递归。请注意，每对括号代表一个新的堆栈帧或递归调用。这个问题的解决方案（即“f”，“fo”或“foo”）在递归结束之前无法推导出来（即基本情况得到满足）。只有最后一帧在“弹出”之前将最后的结果返回到上一个帧中，反之亦然。

理论上，每次调用都会创建一个新的堆栈帧（或作用域），以保存被返回和收集的碎片化解决方案的“位置”。这可能会导致stackoverflow（此链接是一个递归）。

尾调用版本看起来像这样：

build_word ['f'; 'o'; 'o'] ""
build_word ['o'; 'o'], "f"
build_word ['o'] ("f" ^ "o")
build_word [] ("f" ^ "o" ^ "o")
"foo"

在这里，累积的结果（通常存储在一个名为accumulator的变量中）正在向前传递。通过优化，尾调用不必创建新的堆栈帧，因为它不必维护先前的堆栈帧。解决方案是“向前”而不是“向后”解决的。

这里有两个版本的build_word函数：

非尾部

let build_word chars = 
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd :: tl -> build_word tl

尾部

let build_word ?(acc = "") chars =
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd::tl -> build_word ~acc:(acc ^ Char.to_string hd) tl

前向递归在@sepp2k的被接受的答案中有很好的解释。

- Pandemonium