“自然递归"的定义是什么? [英] What is the definition of "natural recursion"?
问题描述
构建列表时，请描述第一个典型元素，然后将其限制为自然递归.
When building a list, describe the first typical element, and then cons it onto the natural recursion.
自然递归"的确切定义是什么?我问的原因是因为我正在上Daniel Daniel的编程语言原理课程，而以下代码不被视为自然递归":
What is the exact definition of "natural recursion"? The reason why I am asking is because I am taking a class on programming language principles by Daniel Friedman and the following code is not considered "naturally recursive":
(define (plus x y)
(if (zero? y) x
(plus (add1 x) (sub1 y))))
但是，以下代码被视为自然递归":
However, the following code is considered "naturally recursive":
(define (plus x y)
(if (zero? y) x
(add1 (plus x (sub1 y)))))
我更喜欢非自然递归"代码，因为它是尾递归的.但是，这样的代码被认为是恶心.当我问到为什么我们不应该以尾部递归形式编写函数时，助理讲师简单地回答:您不会对自然递归感到困惑."
I prefer the "unnaturally recursive" code because it is tail recursive. However, such code is considered anathema. When I asked as to why we shouldn't write the function in tail recursive form then the associate instructor simply replied, "You don't mess with the natural recursion."
以自然递归"形式编写函数有什么优势?
What's the advantage of writing the function in the "naturally recursive" form?
推荐答案
自然"(或只是结构")递归是开始教学生有关递归的最佳方法.这是因为它具有约书亚·泰勒(Joshua Taylor)指出的绝妙保证:它保证终止[*].学生有足够的时间将自己的脑袋缠在这种程序上，以致于将其作为规则"可以为他们节省大量的反对墙撞墙的行为.
"Natural" (or just "Structural") recursion is the best way to start teaching students about recursion. This is because it has the wonderful guarantee that Joshua Taylor points out: it's guaranteed to terminate[*]. Students have a hard enough time wrapping their heads around this kind of program that making this a "rule" can save them a huge amount of head-against-wall-banging.
当您选择离开结构递归的领域时，您(程序员)承担了另外的责任，即确保您的程序在所有输入上都停止运行；考虑&是另一回事证明.
When you choose to leave the realm of structural recursion, you (the programmer) have taken on an additional responsibility, which is to ensure that your program halts on all inputs; it's one more thing to think about & prove.
就您而言，它有些微妙.您有两个 参数，并且要在第二个参数上进行结构递归调用.实际上，根据这种观察(程序在参数2上在结构上是递归的)，我认为您的 原始程序与非尾调用程序一样合法，因为它继承了相同的程序.收敛证明.向Dan询问此事；我很想听听他怎么说.
In your case, it's a bit more subtle. You have two arguments, and you're making structurally recursive calls on the second one. In fact, with this observation (program is structurally recursive on argument 2), I would argue that your original program is pretty much just as legitimate as the non-tail-calling one, since it inherits the same proof-of-convergence. Ask Dan about this; I'd be interested to hear what he has to say.
[*]在这里准确地说，您必须立法规定所有其他愚蠢的东西，例如对不终止的其他函数的调用等.
[*] To be precise here you have to legislate out all kinds of other goofy stuff like calls to other functions that don't terminate, etc.
这篇关于“自然递归"的定义是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
