面试题：C++ 中如何通过优化递归防止堆栈溢出

Question

在C++中，递归调用是导致堆栈溢出的常见原因之一。请描述一种通过优化递归算法来预防堆栈溢出的方法，并给出一个简单的代码示例。

Answer 1

方法描述

将递归算法转换为迭代算法是预防堆栈溢出的常见方法。递归是函数调用自身，每一次调用都会在栈上分配新的空间，当递归深度过大时就容易导致栈溢出。而迭代通过循环来实现同样的逻辑，它使用的是堆空间或者自身的局部变量，避免了栈空间的过度消耗。

代码示例

以计算阶乘为例，传统的递归实现如下：

#include <iostream>

// 递归计算阶乘
int factorial_recursive(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial_recursive(n - 1);
}

使用迭代方式优化后的代码如下：

#include <iostream>

// 迭代计算阶乘
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

在主函数中可以这样调用：

int main() {
    int num = 5;
    std::cout << "递归计算 " << num << " 的阶乘: " << factorial_recursive(num) << std::endl;
    std::cout << "迭代计算 " << num << " 的阶乘: " << factorial_iterative(num) << std::endl;
    return 0;
}

在这个例子中，factorial_iterative函数通过迭代方式计算阶乘，避免了递归调用带来的栈溢出风险。