Scheme中的尾递归，解码树

Question

我不确定尾递归和一般递归的区别。下面的代码为什么不是尾递归，怎样才能使其成为尾递归？

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
    (let ((next-branch
      (choose-branch (car bits) current-branch)))
        (if (leaf? next-branch)
          (cons (symbol-leaf next-branch)
            (decode-1 (cdr bits) tree))
         (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

下面的代码（关于尾递归过程）我做错了什么？

(define (decode2 bits tree)
  (define (decode-1 bits current-branch res)
     (if (null? bits)
       (reverse res)
       (let ((next-branch
            (choose-branch (car bits) current-branch)))
            (if (leaf? next-branch)
                (decode-1 (cdr bits) tree (cons (symbol-leaf next branch) res))
                (decode-1 (cdr bits) tree res)))))
      (decode-1 '() tree res)) 

- N.A.

Answer 1

在下面的代码中，您使用 (decode-1 ...) 的结果作为 cons 的参数：

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))  ;; << here
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

当前递归级别的结果不是由函数调用（即递归调用）直接计算出来的，而是将此结果与另一个值组合起来构建结果。这意味着，在计算对“decode-1”的递归调用时，运行时必须跟踪计算的本地状态（称为帧），以便能够使用“cons”构建结果列表。这使得所有递归调用都像堆栈一样等待其它递归调用。

通过递归终止函数，您可以在递归调用自身之前丢弃当前调用的所有状态：在递归调用返回时不需要保留任何状态：这是允许解释器（或编译器）将调用替换为跳转的条件（这可能不是递归调用，尾调用消除可能发生在任何函数中）。

您可以向“decode-1”添加一个额外的参数（通常称为“累加器”），这里是要返回的列表。例如，您可以将其命名为“res”表示结果。最初它是空列表。

当您到达“（null？bits）”时，您返回到目前为止计算出的列表“res”。该列表可能会倒序排列，因此您可能希望反转它（这也可以递归终止）。

在递归的一般情况下，您调用：

(decode-1 (cdr bits)
          tree 
          (cons (symbol-leaf next-branch) res))

换句话说，你首先建立一个列表，计算(cdr bits)等（理论上没有特定顺序），然后将这三个值全部传递给decode-1:当该调用返回时，它将恰好是你想要传递给最高层调用的返回值，因此在函数中无需跟踪任何其他变量。

- coredump

Answer 2

尾递归是指递归调用是最后发生的事情 - 即递归调用处于“尾部位置”。

正如coredump在他的回答中所解释的那样，如果递归调用之后没有其他操作，则函数是尾递归的。

关注尾递归的原因是它比“常规”递归更高效。

如果递归之后不需要执行任何操作，则可以将递归调用替换为“跳转到函数顶部”。这意味着您避免了函数调用和相关的调用堆栈。

将函数转换为尾递归的常用模式是向函数添加累加器参数，以显式地保存中间结果（而不是隐式地使用调用堆栈）。

---

这是一个使用常规递归和尾递归实现的阶乘函数示例。

常规递归：

(define (fact n)
        (if (= n 0) 1
            (* n (fact (- n 1)))))

使用尾递归加累加器（`acc`）的方法：

(define (fact-tail n)
        (define (fact-helper n acc)
                (if (= n 0) acc
                    (fact-helper (- n 1) (* acc n))))
        (fact-helper n 1))

---

FWIW 有些人在函数式编程的上下文中区分“递归”和“迭代”，并且当他们谈论“迭代”时，意味着尾递归。

请参阅以下链接以了解该概念的另一种介绍：

• https://www.cs.rhodes.edu/~kirlinp/courses/proglang/s13/360-lect5-slides.pdf
• Does tail recursion necessarily need an accumulator?
• https://wiki.c2.com/?TailRecursion

- Morten Jensen

---

那么，一个尾递归过程是迭代过程，这是正确的吗？ - N.A.

@N.A. 它很快变成了一个语义讨论。什么是迭代？例如，在Scheme中，您没有 for 或 while 循环，所以递归被用于迭代，但在C/C ++中，您根本不会将迭代与递归等同 ¯_(ツ)_/¯ 但是在我看来，这是旧的FP文献中一种相当常见的惯例。 - Morten Jensen