面试题：C++中导致堆栈溢出的常见递归场景及预防

Question

在C++编程中，递归函数是导致堆栈溢出的常见原因之一。请举例说明一种可能因递归引发堆栈溢出的场景，并阐述至少两种预防该场景下堆栈溢出的方法。

Answer 1

可能因递归引发堆栈溢出的场景举例

假设有一个计算阶乘的递归函数如下：

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

如果在调用这个函数时传入一个非常大的数，例如 factorial(10000)，随着递归的不断深入，函数调用会在栈上不断创建新的栈帧，而栈的大小是有限的，最终会导致堆栈溢出。

预防该场景下堆栈溢出的方法

1. 尾递归优化： 尾递归是指递归调用是函数的最后一个操作。可以对上述阶乘函数进行尾递归改写：

int factorial_helper(int n, int acc = 1) {
    if (n == 0 || n == 1) {
        return acc;
    } else {
        return factorial_helper(n - 1, n * acc);
    }
}
int factorial(int n) {
    return factorial_helper(n);
}

一些编译器能够对尾递归进行优化，不会不断创建新的栈帧，而是复用当前栈帧，从而避免堆栈溢出。

2. 使用迭代替代递归：

int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

迭代方式使用循环来实现相同的功能，不会在栈上创建大量的递归栈帧，也就不会出现因递归过深导致的堆栈溢出问题。