scheme - 为什么方案中的所有实现都需要尾递归？

Question

尾递归更有效，因为它重用相同的堆栈帧而不是创建新的堆栈帧，但为什么方案中的所有内容都需要这样做？

Answer 1

Scheme 没有 goto，因此所有循环最终都是使用尾递归完成的。如果没有适当的尾递归保证，就没有可靠的方法在 Scheme 中提供循环。

---

更新:我想解释一下“最终使用尾递归”的意思。让我们看看 do 宏，因为@newacct 提到了它。例如:

(do ((i 1 (+ i 1)))
    ((> i 10))
  (display i)
  (newline))

正如我提到的，Scheme 没有 goto，因此它必须从某个地方获取它的循环。它实际上宏扩展为(类似于):

(let loop ((i 1))
  (unless (> i 10)
    (display i)
    (newline)
    (loop (+ i 1))))

注意这里的 loop 不是关键字或内置函数。它是由命名的 let^† 创建的命名函数，它在 unless 形式的底部被调用(通过尾递归) .

实际上，Scheme 中的所有标准循环形式都使用尾递归。无法摆脱它。

---

† 以下是名为 let(松散地说^‡)的宏扩展为:

(letrec ((loop (lambda (i)
                 (unless (> i 10)
                   (display i)
                   (newline)
                   (loop (+ i 1))))))
  (loop 1))

‡ 严格来说，它宏扩展为:

((letrec ((loop (lambda (i)
                  (unless (> i 10)
                    (display i)
                    (newline)
                    (loop (+ i 1))))))
   loop)
 1)