"natural recursion"的定义是什么？
What is the definition of "natural recursion"?
The Third Commandment of The Little Schemer 状态：
When building a list, describe the first typical element, and then cons it onto the natural recursion.
"natural recursion" 的确切定义是什么？我问的原因是因为我正在学习 Daniel Friedman 的编程语言原理 class 并且不考虑以下代码 "naturally recursive":
(define (plus x y)
(if (zero? y) x
(plus (add1 x) (sub1 y))))
但是下面的代码被认为是"naturally recursive":
(define (plus x y)
(if (zero? y) x
(add1 (plus x (sub1 y)))))
我更喜欢 "unnaturally recursive" 代码，因为它是尾递归的。然而，这样的代码被认为是一种诅咒。当我问到为什么我们不应该以尾递归形式编写函数时，副讲师简单地回答说，"You don't mess with the natural recursion."
函数写成"naturally recursive"形式有什么好处？
(define (plus x y)
(if (zero? y) x
(add1 (plus x (sub1 y)))))
当 y != 0 时，它必须记住，一旦 (plus x (sub1 y)) 的结果已知，它就必须对其计算 add1。因此，当 y 达到零时，递归处于最深层次。现在 回溯阶段 开始并执行 add1。这个过程可以用trace.
观察
我跟踪了 :
(require racket/trace)
(define (add1 x) ...)
(define (sub1 x) ...)
(define (plus x y) ...)
(trace plus)
(plus 2 3)
跟踪记录如下：
>(plus 2 3)
> (plus 2 2)
> >(plus 2 1)
> > (plus 2 0) // Deepest point of recursion
< < 2 // Backtracking begins, performing add1 on the results
< <3
< 4
<5
5 // Result
不同的是另一个版本没有回溯阶段。它会调用自己几次，但它是迭代的，因为它正在记住中间结果（作为参数传递）。因此，该过程不会消耗额外的 space.
有时实现尾递归过程比编写它的迭代等效过程更容易或更优雅。但出于某些目的，您可以 not/may 不以递归方式实现它。
PS ：我有一个 class ，它涵盖了一些关于垃圾收集算法的内容。此类算法可能不是递归的，因为可能没有 space 剩余，因此没有 space 用于递归。我记得一个叫做 "Deutsch-Schorr-Waite" 的算法一开始真的很难理解。首先他实现了递归版本只是为了理解这个概念，然后他写了迭代版本（因此必须手动记住他从哪里来的记忆），相信我递归版本更容易但不能在实践中使用......
自然递归与 "natural" 有关，您正在处理的类型的递归定义。在这里，您正在处理自然数；由于 "obviously" 一个自然数要么是零，要么是另一个自然数的后继，当你想构建一个自然数时，你自然会输出 0 或 (add1 z) 其他自然数 z 这恰好是递归计算的。
老师可能希望你在递归类型定义和该类型值的递归处理之间做出link。你不会遇到你遇到的那种问题如果您尝试处理树或列表，请使用数字，因为您经常在 "unnatural ways" 中使用自然数，因此，您可能会很自然地反对使用教会数字来思考。
您已经知道如何编写尾递归函数这一事实与该上下文无关：这显然不是您老师谈论尾调用优化的 objective，至少现在.
副讲师一开始不是很有帮助（"messing with natural recursion"听起来像"don't ask"），但是he/she在您提供的快照中给出的详细解释更合适。
"Natural"（或 "Structural"）递归是开始向学生教授递归的最佳方式。这是因为它具有 Joshua Taylor 指出的美妙保证：它保证终止 [*]。学生们花了足够多的时间思考这种程序，因此 "rule" 可以让他们避免大量的头撞墙。
当您选择离开结构递归领域时，您（程序员）承担了额外的责任，即确保您的程序在所有输入上都停止；这是另一回事需要思考和证明。
在你的情况下，它有点微妙。您有 两个 个参数，并且您正在对第二个参数进行结构递归调用。事实上，通过这种观察（程序在参数 2 上是结构递归的），我认为 你的 原始程序几乎与非尾调用程序一样合法，因为它继承相同的收敛证明。问丹这件事；我很想听听他要说什么。
[*] 在这里准确地说，你必须立法排除所有其他愚蠢的东西，比如调用其他不终止的函数等。
The Third Commandment of The Little Schemer 状态：
When building a list, describe the first typical element, and then cons it onto the natural recursion.
"natural recursion" 的确切定义是什么？我问的原因是因为我正在学习 Daniel Friedman 的编程语言原理 class 并且不考虑以下代码 "naturally recursive":
(define (plus x y)
(if (zero? y) x
(plus (add1 x) (sub1 y))))
但是下面的代码被认为是"naturally recursive":
(define (plus x y)
(if (zero? y) x
(add1 (plus x (sub1 y)))))
我更喜欢 "unnaturally recursive" 代码，因为它是尾递归的。然而，这样的代码被认为是一种诅咒。当我问到为什么我们不应该以尾递归形式编写函数时，副讲师简单地回答说，"You don't mess with the natural recursion."
函数写成"naturally recursive"形式有什么好处？
(define (plus x y)
(if (zero? y) x
(add1 (plus x (sub1 y)))))
当 y != 0 时，它必须记住，一旦 (plus x (sub1 y)) 的结果已知，它就必须对其计算 add1。因此，当 y 达到零时，递归处于最深层次。现在 回溯阶段 开始并执行 add1。这个过程可以用trace.
我跟踪了 :
(require racket/trace)
(define (add1 x) ...)
(define (sub1 x) ...)
(define (plus x y) ...)
(trace plus)
(plus 2 3)
跟踪记录如下：
>(plus 2 3)
> (plus 2 2)
> >(plus 2 1)
> > (plus 2 0) // Deepest point of recursion
< < 2 // Backtracking begins, performing add1 on the results
< <3
< 4
<5
5 // Result
不同的是另一个版本没有回溯阶段。它会调用自己几次，但它是迭代的，因为它正在记住中间结果（作为参数传递）。因此，该过程不会消耗额外的 space.
有时实现尾递归过程比编写它的迭代等效过程更容易或更优雅。但出于某些目的，您可以 not/may 不以递归方式实现它。
PS ：我有一个 class ，它涵盖了一些关于垃圾收集算法的内容。此类算法可能不是递归的，因为可能没有 space 剩余，因此没有 space 用于递归。我记得一个叫做 "Deutsch-Schorr-Waite" 的算法一开始真的很难理解。首先他实现了递归版本只是为了理解这个概念，然后他写了迭代版本（因此必须手动记住他从哪里来的记忆），相信我递归版本更容易但不能在实践中使用......
自然递归与 "natural" 有关，您正在处理的类型的递归定义。在这里，您正在处理自然数；由于 "obviously" 一个自然数要么是零，要么是另一个自然数的后继，当你想构建一个自然数时，你自然会输出 0 或 (add1 z) 其他自然数 z 这恰好是递归计算的。
老师可能希望你在递归类型定义和该类型值的递归处理之间做出link。你不会遇到你遇到的那种问题如果您尝试处理树或列表，请使用数字，因为您经常在 "unnatural ways" 中使用自然数，因此，您可能会很自然地反对使用教会数字来思考。
您已经知道如何编写尾递归函数这一事实与该上下文无关：这显然不是您老师谈论尾调用优化的 objective，至少现在.
副讲师一开始不是很有帮助（"messing with natural recursion"听起来像"don't ask"），但是he/she在您提供的快照中给出的详细解释更合适。
"Natural"（或 "Structural"）递归是开始向学生教授递归的最佳方式。这是因为它具有 Joshua Taylor 指出的美妙保证：它保证终止 [*]。学生们花了足够多的时间思考这种程序，因此 "rule" 可以让他们避免大量的头撞墙。
当您选择离开结构递归领域时，您（程序员）承担了额外的责任，即确保您的程序在所有输入上都停止；这是另一回事需要思考和证明。
在你的情况下，它有点微妙。您有 两个 个参数，并且您正在对第二个参数进行结构递归调用。事实上，通过这种观察（程序在参数 2 上是结构递归的），我认为 你的 原始程序几乎与非尾调用程序一样合法，因为它继承相同的收敛证明。问丹这件事；我很想听听他要说什么。
[*] 在这里准确地说，你必须立法排除所有其他愚蠢的东西，比如调用其他不终止的函数等。