12

小谋士的第三条诫命说：

构建列表时，描述第一个典型元素，然后将其用于自然递归。

“自然递归”的确切定义是什么？我问的原因是因为我正在上丹尼尔弗里德曼的编程语言原则课程，并且以下代码不被认为是“自然递归的”：

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

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

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

4

3 回答 3

9

“自然”（或只是“结构”）递归是开始向学生教授递归的最佳方式。这是因为它有 Joshua Taylor 指出的美妙保证：保证终止[*]。学生们很难将他们的头脑围绕在这种程序上，将其作为“规则”可以为他们节省大量的头撞墙。

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

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

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

于 2015-08-28T17:30:39.233 回答
6

自然递归与您正在处理的类型的“自然”递归定义有关。在这里，您正在处理自然数；因为“显然”一个自然数要么是零，要么是另一个自然数的后继，所以当你想构建一个自然数时，你自然会输出0或(add1 z)其他一些z恰好是递归计算的自然数。

老师可能希望您在递归类型定义和该类型值的递归处理之间建立联系。如果您尝试处理树或列表，则不会遇到数字问题，因为您经常以“不自然的方式”使用自然数，因此，您可能会自然反对以教堂数字的方式思考。

你已经知道如何编写尾递归函数的事实在这种情况下是无关紧要的：这显然不是你的老师谈论尾调用优化的目标，至少现在是这样。

助理讲师起初并没有太大帮助（“搞乱自然递归”听起来像“不要问”），但他/她在您提供的快照中给出的详细解释更合适。

于 2015-08-28T08:30:59.057 回答
1 
(define (plus x y)
(if (zero? y) x
    (add1 (plus x (sub1 y)))))

当y != 0它必须记住，一旦(plus x (sub1 y))知道结果，它就必须对其进行计算add1。因此，当 y 达到零时，递归处于最深处。现在回溯阶段开始并add1执行 's。可以使用 观察此过程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

不同的是，另一个版本没有回溯阶段。它会调用自己几次，但它是迭代的，因为它正在记住中间结果（作为参数传递）。因此，该过程不会消耗额外的空间。

有时实现尾递归过程比编写它的迭代等价物更容易或更优雅。但是出于某些目的，您不能/可能不会以递归方式实现它。

PS：我有一堂课讲了一些关于垃圾收集算法的内容。这样的算法可能不是递归的，因为可能没有剩余空间，因此没有空间用于递归。我记得一种叫做“Deutsch-Schorr-Waite”的算法，一开始真的很难理解。首先他实现了递归版本只是为了理解这个概念，然后他编写了迭代版本（因此必须手动记住他从哪里来），相信我递归版本更容易但不能在实践中使用......

于 2015-08-27T23:53:07.573 回答