面试题：C++ 中递归函数性能优化之栈溢出处理

Question

在C++中，编写一个递归函数用于计算斐波那契数列。假设在实际应用场景下，由于递归深度较深可能导致栈溢出问题，描述你会采取哪些措施来优化该递归函数以避免栈溢出，同时不改变函数的递归逻辑，并展示优化后的代码。

Answer 1

避免栈溢出的措施

1. 尾递归优化：将递归函数改写为尾递归形式，尾递归是指在递归调用返回时，除了返回递归调用的结果外，不再进行其他操作。现代编译器通常能够对尾递归进行优化，将其转换为迭代形式，从而避免栈溢出。
2. 手动模拟栈：使用栈数据结构手动模拟递归调用过程，通过循环来控制递归的执行，这样可以避免系统栈的深度限制。

优化后的代码（尾递归优化）

#include <iostream>

// 尾递归辅助函数
unsigned long long fibonacci_helper(unsigned long long a, unsigned long long b, int n) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fibonacci_helper(b, a + b, n - 1);
}

// 主递归函数
unsigned long long fibonacci(int n) {
    return fibonacci_helper(0, 1, n);
}

int main() {
    int n = 10; // 示例值
    std::cout << "Fibonacci number at position " << n << " is: " << fibonacci(n) << std::endl;
    return 0;
}

优化后的代码（手动模拟栈）

#include <iostream>
#include <stack>

struct RecursionFrame {
    int n;
    unsigned long long a;
    unsigned long long b;
    int step; // 用于记录递归执行到哪一步
    RecursionFrame(int n, unsigned long long a, unsigned long long b, int step)
        : n(n), a(a), b(b), step(step) {}
};

unsigned long long fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    std::stack<RecursionFrame> stack;
    stack.push(RecursionFrame(n, 0, 1, 0));

    while (!stack.empty()) {
        RecursionFrame& frame = stack.top();
        if (frame.step == 0) {
            if (frame.n == 0) {
                stack.pop();
                if (!stack.empty()) {
                    stack.top().a += frame.a;
                }
                continue;
            }
            if (frame.n == 1) {
                stack.pop();
                if (!stack.empty()) {
                    stack.top().a += frame.b;
                }
                continue;
            }
            stack.push(RecursionFrame(frame.n - 1, frame.b, frame.a + frame.b, 0));
            frame.step = 1;
        } else {
            stack.pop();
            if (!stack.empty()) {
                stack.top().a += frame.a;
            }
        }
    }
    return stack.empty()? 0 : stack.top().a;
}

int main() {
    int n = 10; // 示例值
    std::cout << "Fibonacci number at position " << n << " is: " << fibonacci(n) << std::endl;
    return 0;
}