1

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

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

如果函数直接或间接调用自身，则它是递归的

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

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

function a() {
    a();
}

还有这个：

function a() {
    b();
}

function b() {
    a();
}

甚至这个：

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

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

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

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

当一个函数被定义为更简单、通常更小的自身版本时，计算机编程中的递归就是一个例子。然后通过组合从问题的更简单版本获得的解决方案来设计问题的解决方案。

所以这是递归的：

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

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

4

4 回答 4

2

递归只是根据该问题的更简单情况（更简单的意思是“更接近”终止条件，不一定实际上更简单）来定义问题，直到最简单的情况是已知的情况（终止条件暗示较早）。因此，例如，常年阶乘函数有一个终止条件：

f(1) = 1

以及用更简单的问题定义问题：

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

我听过的最好的解释是：

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

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

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

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

因此除了测试堆栈溢出时会发生什么之外，不太可能有任何好处:-)

于 2013-07-17T08:58:34.117 回答
2

递归的定义？再次阅读这一行，直到你明白为止。

（具有中止标准以防止无限循环的自调用函数）。

于 2013-07-17T08:54:56.380 回答
2

递归是赋予调用自身的函数的名称。现在无论函数是否无限调用自身......它仍然是一个递归。

不一定要将问题划分为子问题。但是，在计算机科学中；递归一词是指一种用于解决问题的技术，通过将问题分解为子问题并且通常问题是有限的。

还有一点，递归是使用堆栈实现的。每个函数调用在堆栈中堆叠在另一个顶部，直到最后一个调用满足基本条件，然后堆栈中的函数从上到下执行。

但是，如果没有基本条件或永远不会满足基本条件。然后对该函数的无限调用将被推送到堆栈，导致内存被填满，并且将引发 stackOverFlow 异常，操作系统通过终止程序来处理它。

关于setTimeout()它是一个异步调用并且与递归无关，它是一个独立的调用，因为调用者函数不依赖于被调用者，无论它是被调用的函数还是另一个。

于 2013-07-17T09:15:44.297 回答
0

从您发布的维基百科：

当一个函数被定义为更简单、通常更小的自身版本时，计算机编程中的递归就是一个例子。然后通过组合从问题的更简单版本获得的解决方案来设计问题的解决方案。

所以。有问题，就有解决办法。有一个自称为最小化主要问题的函数。这个函数是递归的。

案子：

function a() {
    a();
}

没有问题，没有什么可以最小化，没有解决方案。这对我来说不是递归的。这只是一个无限循环。

再举一个例子：

function a(n) {
    if(n<.5) {
        return n+a(Math.random());
    }else {
        return n;
    }
}
console.log(a(.3));

这是递归的吗？不，可能存在问题，但没有找到解决方案以最小化主要问题。很简单，它会随机调用自己，直到某个标志为真。同样，这是一个循环。setTimeout 或 setInterval 也会发生同样的情况（问题的解决方案将取决于系统调用）。

于 2013-07-17T09:37:47.837 回答