尾递归与前向递归

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 

这是向前递推，正如你可以看到它比落后的递归variant稍微繁琐，因为它需要辅助功能。现在这不是尾递归，因为最后一次调用loop是乘法，而不是递归。因此，为了使尾递归，你会做这样的事情：

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

现在，这既是前向递归和尾递归，因为递归调用是）一个尾调用和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 

尾部递归函数使用的储液器，一个，以存储前一次调用结果的值。这允许OCaml执行尾部呼叫优化，从而导致堆栈不会溢出。通常，尾递归函数将使用累加器值来允许尾部调用优化发生。

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。