C++实现递归函数的方法

C++中实现递归函数其实是一种函数自我调用的方式。在实现递归函数时，需要注意以下几点：

1.要分清递归的边界条件，一旦达到边界条件，递归函数就不再执行自己。

2.递归的过程中可能会引起栈溢出，为此需要设置递归函数的最大递归次数，避免无限递归。

以下是实现递归函数的详细步骤：

1.编写递归函数的函数体

递归函数的函数体即为要实现的递归过程。在函数体中需要使用到递归调用，即在函数体中使用函数自身。因此，在编写递归函数时需要考虑几个问题：

• 函数在何时结束递归调用，即边界条件是什么？
• 在递归调用时，如何将参数传递给下一次调用？
• 在递归调用的过程中，如何处理函数返回值？

示例 1：计算n的阶乘

int factorial(int n) {
    if (n == 0 || n == 1) { // 边界条件
        return 1;
    } else {
        return n * factorial(n - 1); // 递归调用
    }
}

2.设置递归函数的出口

递归函数会不断地调用自身，直到满足某个条件终止递归。为了保证函数调用不会无限制地进行下去，需要设置一个递归出口，即满足该条件则不再进行递归调用。

示例 2：斐波那契数列

int fibonacci(int n) {
    if (n == 1 || n == 2) { // 边界条件
        return 1;
    } else if (n <= 0) { // 非法输入
        return -1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
    }
}

在上述的例子中，当n == 1或n == 2时，递归会终止。此时，不再进行递归调用，直接返回1。如果n <= 0，则表示输入非法，此时返回-1。

3.设置最大递归次数

在进行递归调用时，可能会导致栈溢出。为避免这种情况的发生，可以设置递归函数的最大递归次数，当递归次数超过最大值时，递归就会强制结束。

示例 3：计算n的阶乘（设置最大递归次数为100）

int factorial(int n, int max_depth, int cur_depth = 0) {
    if (n == 0 || n == 1) { // 边界条件
        return 1;
    } else if (cur_depth > max_depth) { // 达到最大递归深度
        return -1;
    } else {
        return n * factorial(n - 1, max_depth, cur_depth + 1); // 递归调用
    }
}

在示例3中，我们新增了两个参数max_depth和cur_depth，max_depth表示最大递归深度，cur_depth表示当前递归深度。在每次递归调用时，将cur_depth加1，当cur_depth超过max_depth时，递归就会终止，返回-1。