math - 递归不仅仅是一个函数调用本身

Question

我见过的关于递归函数的每一本教科书都以阶乘为例，这很有帮助，但并不完全有启发性。

出于编程目的，递归函数是否可以将一个函数作为其基本情况，它是否可以在其主体中包含其他函数调用，或者它是否可以在不同的递归级别以不同的方式执行？

如果它做了这些事情中的任何一件，它仍然是一个“递归函数”还是现在是别的东西？

Answer 1

递归函数的定义只是“一个调用自身的函数”。所以如果你有一个调用自己的函数，它就是一个递归函数。

其他任何事情都取决于您正在使用的语言的功能。

Answer 2

这是一个相当简单的递归函数示例，它简单地将集合（表示为堆栈的数组）中的所有值输出到浏览器控制台，因为它使用 .pop() 方法将它们从堆栈中弹出。

totalSize 值不会在整个调用堆栈中发生变化，因此它可用于通过将当前堆栈大小除以原始大小来测量中间点。

要回答它能否在递归的不同级别表现不同的问题，答案是肯定的：

// a simple array of 10 items
var coll = [1,2,3,4,5,6,7,8,9,10];

// recursive function that calls itself. It behaves slightly different at
 // the halfway point
function test(totalSize, col) {
    if(col == undefined || col.length == 0) {
        return 0;

     } else {
        if(col.length / totalSize < .5) {
            console.log("Past 1/2 way point!");
        }
        console.log("total = " + totalSize);
        console.log("col.pop() = " + col.pop());
        return test(totalSize, col);
    }
}

// make a call to the function with the total size and the collection
test(coll.length, coll);

另外，您还问是否可以调用其他函数，这也是可以的。在下面的例子中，一个函数用于返回基本情况的结果，一个函数用于抽象中点行为：

// a simple array of 10 items
var coll = [1,2,3,4,5,6,7,8,9,10];

// recursive function that calls itself. It behaves slightly different at
 // the halfway point
function test(totalSize, col) {
    if(col == undefined || col.length == 0) {
        return handleBaseCase(totalSize, col);

     } else {
        // handle if it's at 1/2 way point
        handleHalfwayPoint(totalSize, col);  

        console.log("tital = " + totalSize);
        console.log("col.pop() = " + col.pop());
        return test(totalSize, col);
    }
}

function handleHalfwayPoint(totalSize, collection) {
    if(collection.length / totalSize < .5) {
        console.log("Past 1/2 way point!");
    }
}

// instead of returning 0, return "Done" and also print to the log
function handleBaseCase(totalSize, collection) {
    console.info("Done!");
    return "Done!";
}

// make a call to the function with the total size and the collection
test(coll.length, coll);

虽然这些特定示例并不能解决任何实际问题，但它展示了在另一个函数中调用一个函数的概念如何扩展以处理其他用例。教科书中的例子只是为了教你递归的基础知识，并帮助你使用必要的工具来处理未来更复杂的现实问题。

由于这种函数式语言是 JavaScript，因此运行它们的障碍很低。您可以通过在 Chrome 开发者控制台中运行代码来尝试这些示例，或者您可以在一个小的测试 HTML 文件中运行它们。祝你好运！

Answer 3

递归函数是在其主体中调用自身一次或多次的函数。函数也可以是相互递归的，其中一个函数是根据第二个函数定义的，反之亦然。

我已经编程了 20 多年而无需递归。让我真正理解递归调用的必要性和美妙之处在于 Scheme 语言，以及诸如“The little Schemer”之类的书籍。

并非所有编程语言都支持同一级别的递归。计划是做得很好的人之一。Python 少得多。因此，如果您想深入研究递归，请检查您的编程语言的能力。

Answer 4

正如其他答案所说，递归函数是一个调用自身的函数。这里解释了两种类型：

1. 直接递归：函数调用自身。
2. 间接递归：当一个函数不是由它自己调用而是由它调用的另一个函数（直接或间接）调用时。

我在你的问题中看到了数学标签。递归与数学归纳有关。如果你证明它可以解决基本情况，然后你证明如果无限序列语句中的任何一个语句为真，那么下一个语句也是如此，你证明它在任何情况下都能解决问题。