javascript - 递归的定义是什么

Question

所以，我们都知道递归函数，对吧？但究竟是什么使函数递归？我在另一个问题 (Lightening effect with javascript) 的评论部分进行了一个小讨论，这在某种程度上挑战了我对递归函数的看法，但它也让我对缺乏适当的定义感到非常不满意。

到目前为止，我个人对递归函数的定义如下:

A function is recursive if it directly or indirectly invokes itself

注意:我将为以下示例提供 JavaScript 代码，但我确信它们非常通用。

这种递归函数的一个简单示例可能是这样的:

function a() {
    a();
}

还有这个:

function a() {
    b();
}

function b() {
    a();
}

甚至这样:

function a() {
    setTimeout(a, 1000);
}

这些函数都不会计算任何东西，但我仍然会认为它们是递归的，因为它们会调用自己。

出现的一件事是，第三个示例不是递归的，因为它使用了 setTimeout 并且因此展开了堆栈。它也不是递归的，因为从第 n 次调用返回后，它不会将控制权交还给第 n-1 次调用。

提出的另一点是，这些函数都不是递归的，因为它们都不以递归的方式计算实际问题。这意味着必须通过将问题分成越来越小的实例来解决问题。这里引用维基百科文章:

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);
}

那么递归函数的正确定义是什么？到底有没有，或者这真的只是一个哲学问题？函数必须具备哪些特征才能被归类为递归？

Answer 1

递归只是根据该问题的更简单情况(更简单意味着“更接近”终止条件，不一定实际上更简单)来定义问题，直到最简单的情况是已知的(前面提到的终止条件)。因此，例如，常年阶乘函数有一个终止条件:

f(1) = 1

以及问题的更简单的定义:

f(n) = n * f(n - 1), for n > 1

我听过的最好的解释是:

1. 如果您是 Donald Knuth，就会明白它是什么。
2. 否则，找一个离唐纳 Derby 较近的人问问他们。

我不会将 setTimeout 称为一次递归，因为 a 实际上是 不 调用自身。相反，它要求“系统”在以后的某个日期调用它。

在某处设置终止条件也很重要。没有它，它仍然是递归，但它是无限递归，与无限循环没有什么不同，例如:

for (i = 0; i < 10; j++) {}

因此除了测试堆栈溢出时发生的情况之外，不可能对任何其他事情有任何好处:-)