C++中使用递归函数

C++中使用递归函数

在有些情况下，可让函数调用它自己，这样的函数称为递归函数。递归函数必须有明确的退出条件，满足这种条件后，函数将返回，而不再调用自己。

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

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

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

• 基本情况（Base Case）：这是递归的终止条件。没有基本情况，递归函数将无限地调用自己，导致栈溢出。
• 递归情况（Recursive Case）：在这里，函数将问题分解成更小的子问题，并自我调用来解决这些子问题。

实际场景中，很多问题适合用递归函数来解决。

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

#include 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

程序运行后，factorial(5) 函数会被调用，这是一个递归函数，它的执行过程如下：

• factorial(5) 被调用，基本情况 n==0 不成立，所以进入递归情况，计算 5*factorial(4)；
• factorial(4) 被调用，基本情况 n==0 不成立，所以进入递归情况，计算 4*factorial(3)；
• factorial(3) 被调用，基本情况 n==0 不成立，所以进入递归情况，计算 3*factorial(2)；
• factorial(2) 被调用，基本情况 n==0 不成立，所以进入递归情况，计算 2*factorial(1)；
• factorial(1) 被调用，基本情况 n==0 不成立，所以进入递归情况，计算 1*factorial(0)；
• factorial(0) 被调用，基本情况 n==0 成立，返回 1。

此时递归开始“展开”，并且每一层递归都会返回其结果：

• factorial(1) 计算 1*1=1，所以返回 1；
• factorial(2) 计算 2*1=2，所以返回 2；
• factorial(3) 计算 3*2=6，所以返回 6；
• factorial(4) 计算 4*6=24，所以返回 24；
• factorial(5) 计算 5*24=120，所以返回 120。

最后在 main() 函数中，factorial(5) 的结果 120 被赋值给变量 result，然后输出到控制台。

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

警告：

如果没有退出条件或存在 bug，递归函数可能不断调用自己，直到栈溢出后才停止，导致应用程序崩溃。
1

计算斐波纳契数列时，递归函数很有用，如程序清单 7.5 所示。该数列的开头两个数为 0 和 1：

F(0) = 0
F(1) = 1
1
2

随后的每个数都是前两个数之和。计算第 n 个数（ n>1）的公式如下：

Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)
1

因此斐波纳契数列如下：

F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8, and so on.
1
2
3
4
5

使用递归函数计算斐波纳契数列中的数字：

#include 
using namespace std;

int GetFibNumber(int fibIndex)
{
    if (fibIndex < 2)
        return fibIndex;
    else // recursion if fibIndex >= 2
        return GetFibNumber(fibIndex - 1) + GetFibNumber(fibIndex - 2);
}

int main()
{
    cout << "Enter 0-based index of desired Fibonacci Number: ";
    int index = 0;
    cin >> index;

    cout << "Fibonacci number is: " << GetFibNumber(index) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出：

Enter 0-based index of desired Fibonacci Number: 6
Fibonacci number is: 8
1
2

分析：

函数 GetFibNumber()是在第 3～9 行定义的，这是一个递归函数，因为它在第 8 行调用了自己。第 5 和 6 行指定了退出条件，确保该函数在 fibIndex 小于 2 时不再递归。鉴于函数 GetFibNumber()调用自己时降低了 fibIndex 的值，因此递归到一定程度后将满足递归条件，从而停止递归，并将计算得到的斐波纳契数返回给 main()。

该文章会更新，欢迎大家批评指正。

推荐一个零声学院的C++服务器开发课程，个人觉得老师讲得不错，
分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，
fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，
TCP/IP，协程，DPDK等技术内容
点击立即学习：C/C++后台高级服务器课程