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

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 的递归调用时跟踪本地计算状态（称为帧），以便能够使用 [= 构建结果列表13=]。这使得所有递归调用一个接一个地等待，就像一个堆栈。

使用递归终端函数，您可以在递归调用自己之前丢弃当前调用的所有状态：递归调用时不应该保留任何必要的状态return：这是条件允许解释器（或编译器）用跳转替换调用（这不需要是递归调用，任何函数都可能发生尾调用消除）。

您可以向 decode-1 添加一个附加参数（通常称为“累加器”），这里是您想要 return 的列表。例如，您可以将其称为 res 作为结果。最初它是空列表。

当你达到 (null? bits) 时，你 return 列表计算到目前为止，res。该列表可能会以相反的顺序排列，因此您可能想要反转它（这也可以成为递归终端）。

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

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

换句话说，您首先构建一个列表，计算 (cdr bits)，等等（理论上没有特定顺序），然后将所有三个值传递给 decode-1：当此调用 returns，它恰好是您要最上面调用 return 的 return 值，因此无需跟踪函数中的任何其他变量。

Answer 2

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

正如 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

Scheme 的尾递归。解码树

Tail recursion with Scheme. Decoding trees

scheme