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)))))
我更喜欢“非自然递归”代码,因为它是尾递归的。然而,这样的代码被认为是一种诅咒。当我问到为什么我们不应该以尾递归形式编写函数时,副讲师简单地回答说,“你不要乱用自然递归。”
以“自然递归”形式编写函数有什么好处?
最佳答案
“自然”(或只是“结构”)递归是开始向学生教授递归的最佳方式。这是因为它具有 Joshua Taylor 指出的美妙保证:它保证终止 [*]。学生们很难花时间思考这类程序,因此将此作为“规则”可以避免他们大量的头撞墙。
当您选择离开结构递归领域时,您(程序员)承担了额外的责任,即确保您的程序在所有输入上停止;这是需要思考和证明的另一件事。
在你的情况下,它有点微妙。您有两个 参数,并且您正在对第二个参数进行结构递归调用。事实上,通过这种观察(程序在参数 2 上是结构递归的),我认为 你的 原始程序几乎与非尾调用程序一样合法,因为它继承了相同的收敛证明。问丹这件事;我很想听听他要说什么。
[*] 在这里准确地说,你必须立法排除所有其他愚蠢的东西,比如调用其他不终止的函数等。
关于recursion - "natural recursion"的定义是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32260444/