recursion - "natural recursion"的定义是什么？

Question

The Third Commandment的 The Little Schemer状态:

When building a list, describe the first typical element, and then cons it onto the natural recursion.

“自然递归”的确切定义是什么？我问的原因是因为我正在上 Daniel Friedman 的编程语言原则类(class)，以下代码不被视为“自然递归”:

(define (plus x y)
    (if (zero? y) x
        (plus (add1 x) (sub1 y))))

但是，下面的代码被认为是“自然递归的”:

(define (plus x y)
    (if (zero? y) x
        (add1 (plus x (sub1 y)))))

我更喜欢“非自然递归”代码，因为它是尾递归的。然而，这样的代码被认为是一种诅咒。当我问到为什么我们不应该以尾递归形式编写函数时，副讲师简单地回答说，“你不要乱用自然递归。”

以“自然递归”形式编写函数有什么好处？

Answer 1

“自然”(或只是“结构”)递归是开始向学生教授递归的最佳方式。这是因为它具有 Joshua Taylor 指出的美妙保证:它保证终止 [*]。学生们很难花时间思考这类程序，因此将此作为“规则”可以避免他们大量的头撞墙。

当您选择离开结构递归领域时，您(程序员)承担了额外的责任，即确保您的程序在所有输入上停止；这是需要思考和证明的另一件事。

在你的情况下，它有点微妙。您有两个 参数，并且您正在对第二个参数进行结构递归调用。事实上，通过这种观察(程序在参数 2 上是结构递归的)，我认为 你的 原始程序几乎与非尾调用程序一样合法，因为它继承了相同的收敛证明。问丹这件事；我很想听听他要说什么。

[*] 在这里准确地说，你必须立法排除所有其他愚蠢的东西，比如调用其他不终止的函数等。