首页 > 编程笔记

C++递归函数（入门必读）

如果一个函数在其定义中又调用自身，则称为递归函数，调用自身的过程叫做递归。

递归分为直接递归和间接递归。直接递归是指函数直接调用自身，间接递归则指 A 函数调用了其它函数，而其它的函数中又调用了 A 函数。

递归函数通常由以下两个部分组成：

实际场景中，很多问题适合用递归函数来解决，接下来通过两个实例，带读者体会函数的递归过程。

实例一

计算一个阶乘（n!）是递归的经典应用之一，求 n! 的递归函数如下：
#include <iostream>

int factorial(int n) {
    // 基本情况
    if (n == 0) {
        return 1;
    }
    // 递归情况
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(5);  // 5的阶乘是120
    std::cout << "Factorial of 5 is: " << result << std::endl;
    return 0;
}
程序运行后，factorial(5) 函数会被调用，这是一个递归函数，它的执行过程如下：

此时递归开始“展开”，并且每一层递归都会返回其结果：
最后在 main() 函数中，factorial(5) 的结果 120 被赋值给变量 result，然后输出到控制台。

因此，这个递归函数的执行过程首先是“深入”（从 factorial(5) 到 factorial(0)），然后是“展开”（从 factorial(0) 返回到 factorial(5)），在这个过程中逐步完成阶乘的计算。每一层递归都依赖于其下一层的结果，直到达到基本情况，然后逐层返回计算结果。

实例二

计算斐波那契数列的第 n 个元素是递归的另一个经典例子。

所谓斐波那契数列，指从 0 和 1 开始，之后每一项都是前两项之和的数列，数列的前几项是 0 1 1 2 3 5 8 13...

计算斐波那契数列的第 n 个元素，对应的递归函数如下：
#include <iostream>

int fibonacci(int n) {
    // 基本情况
    if (n == 0) return 0;
    if (n == 1) return 1;
    // 递归情况
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int result = fibonacci(5);  // 第5个Fibonacci数是5
    std::cout << "The 5th Fibonacci number is: " << result << std::endl;
    return 0;
}
示例程序中，main() 函数调用了 fibonacci(5)，也就是计算斐波那契数列的第 5 个元素。

fibonacci() 是一个递归函数，它的执行过程是：
至此递归开始“展开”，并且每一层递归都会返回其结果：
最终，fibonacci(5) 的返回值是 5，这个结果存储在 result 变量中，并输出到控制台。

虽然递归在解决某些问题方面非常方便，但也是有代价的。每次递归调用都要重新创建一份函数的副本，如果函数中有大量的变量，并且递归层次很多，则内存很快就会被消耗殆尽。因此应用递归时，函数应当尽量简单，而且要尽量减少递归的层次。

推荐阅读