Aad*_*hah 9 lisp recursion scheme the-little-schemer racket
在构建列表时,描述第一个典型元素,然后将其纳入自然递归.
"自然递归"的确切定义是什么？我问的原因是因为我正在接受Daniel Friedman的编程语言原则课程,以下代码不被认为是"自然递归":
(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上是递归的),我认为你的原始程序与非尾部调用程序一样合法,因为它继承了相同的收敛证明.问丹这件事; 我很想知道他要说些什么.
[*]在这里,你必须立法规定各种其他愚蠢的东西,比如对不终止的其他功能的调用,等等.
自然递归与您正在处理的类型的"自然"递归定义有关.在这里,你正在使用自然数; 因为"显然"一个自然数是零或另一个自然数的后继,当你想建立一个自然数时,你自然输出0或者(add1 z)其他一些z恰好以递归方式计算的自然数.
教师可能希望您在递归类型定义和递归处理该类型的值之间建立链接.如果你试图处理树或列表,你不会遇到数字问题,因为你经常以"不自然的方式"使用自然数字,因此,你可能会对教会数字有自然的反对意见.
您已经知道如何编写尾递归函数的事实在这种情况下是无关紧要的:至少就目前而言,这显然不是您的老师谈论尾部调用优化的目标.
副教练起初并不是很有帮助("乱搞自然递归"的声音为"不要问"),但他/她在你给的快照中给出的详细解释更合适.