Recursion的解释是什么 [英] What is the Definition of Recursion
问题描述
所以，我们都知道递归函数，对吗?但是究竟是什么使函数递归呢?我在另一个问题的评论部分进行了简短的讨论(使用JavaScript减轻效果)这种方法挑战了我对递归函数的看法，但也使我感到非常不满意，缺乏适当的定义.
So, we all know recursive functions, right? But what exactly is it, that makes a function recursive? I had a small discussion in the comment section of another question (Lightening effect with javascript) that kind of challenged my view of recursive functions but it also left me with a quite unsatisfying lack of proper definition.
到目前为止，我对递归函数的个人定义如下:
My personal definition of recursive functions so far was the following:
如果函数直接或间接调用自身，则该函数是递归的
A function is recursive if it directly or indirectly invokes itself
注意::我将为以下示例提供JavaScript代码，但我确定它们非常通用.
Note: I will provide JavaScript code for the following examples, but I'm sure they are pretty universal.
此类递归函数的一个简单示例可能是:
A simple example for such a recursive function could be this:
function a() {
a();
}
但这也是
function a() {
b();
}
function b() {
a();
}
甚至这个:
function a() {
setTimeout(a, 1000);
}
这些函数都不计算任何东西，但是我仍然会认为它们是递归的，只是因为它们调用了自己.
None of those functions computes anything but I would have still considered them recursive just because they invoke themselves.
出现的一件事是，第三个示例不是递归的，因为它使用了 setTimeout ，因此堆栈未展开.它也不是递归的，因为从第n次调用返回后，它没有将控制权交还给第n-1次调用.
One thing that came up was, that the third example is not recursive because it uses setTimeout and therefor the stack is unwound. It also isn't recursive because after returning from the nth invocation it doesn't give back control to the n-1th invocation.
提出的另一点是，这些函数都不是递归的，因为它们都不以递归的方式计算实际问题.这意味着必须通过将问题分成越来越小的实例来解决问题.这是引用的维基百科文章:
Another point, that was raised, was that none of those functions were recursive because they all don't compute an actual problem in a recursive way. Meaning that a problem has to be solved by dividing it in smaller and smaller instances. Here the quoted Wikipedia article:
以函数为例说明计算机编程中的递归以本身更简单，通常更小的版本来定义.这然后通过组合解决方案来设计问题的解决方案从问题的简单版本获得.
Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem.
所以这是递归的:
function fac(n) {
if (n <= 0) {
return 1;
}
return n * fac(n - 1);
}
但这不是:
function fac(n) {
if (n <= 0) {
return 1;
}
console.log(n);
fac(n - 1);
}
那么递归函数的正确定义是什么?到底有没有还是真的只是一个哲学问题?函数必须具有哪些功能才能进行递归分类?
So what is the proper definition of a recursive function? Is there any at all or is it really just a philosophical question? What features must a function have, in order to be classified recursive?
推荐答案
递归只是根据一个更简单的情况(一个简单的意思是更接近于"终止条件，而不一定是实际上)来定义问题.直到最简单的情况是已知的情况(前面提到的终止条件).因此，例如，多年生阶乘函数具有终止条件:
Recursion is simply defining a problem in terms of a simpler case (simpler meaning "closer" to the terminating condition, not necessarily actually simpler) of that problem, down to the point where the simplest case is a known one (the terminating condition alluded to earlier). So, for example, the perennial factorial function has a terminating condition:
f(1) = 1
以及用一个简单的问题来定义问题:
and the definition of the problem in terms of a simpler one:
f(n) = n * f(n - 1), for n > 1
我听说过的最好的解释是:
The best explanation of it that I ever heard was this:
- 如果您是Donald Knuth，那么您会明白它是什么.
- 否则，找一个更接近唐纳德的人并问他们.
我不会将 setTimeout 称为一次递归，因为 a 实际上不是 本身.取而代之的是，它要求系统"稍后再调用它.
I wouldn't call the setTimeout one recursion because a is not actually calling itself. Instead, it's asking the "system" to call it at some later date.
将终止条件放在某处也很重要.没有这个，它仍然是递归的，但是它是 infinite 的递归，与无限循环类似，如:
It's also important to have the terminating condition in there somewhere. Without that, it's still recursion but it's infinite recursion, no different to infinite loops like:
for (i = 0; i < 10; j++) {}
，因此除了测试堆栈溢出时会发生什么以外，除了其他可能没有什么好处:-)
and hence unlikely to be any good for anything other than testing what happens when your stack overflows :-)
这篇关于Recursion的解释是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
