汉诺塔递归解法栈溢出问题：为何递归跳跃思想失效？

问题背景 #

经典汉诺塔要求：3根柱子、N个不同大小圆盘，初始时圆盘在第一根柱子上从小到大叠放，遵循3条规则：

• 每次只能移动一个圆盘
• 只能从柱子顶端移动圆盘
• 圆盘不能放在更小的圆盘上

目标是将圆盘从第一根柱子（A）移到最后一根（C），示例输入A=[2,1,0]时输出C=[2,1,0]。我采用“递归跳跃思想”编写了C++代码，但运行时触发栈溢出错误：

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        if (A.size() == 0) {
            return;
        }
        int base = A.front();
        A.erase(A.begin());
        hanota(A, C, B);
        C.push_back(base);
        hanota(B, A, C);
    }
};

错误信息：

AddressSanitizer: DEADLYSIGNAL
==================================================================
==20==
ERROR: AddressSanitizer: 
stack-overflow on address 0x7ffc5b035f48 
(pc 0x00000031f5ee bp 0x7ffc5b036790 sp 0x7ffc5b035f50 T0) 
==20==
ABORTING

疑问：为何递归跳跃思想在此失效？是否与终止条件设置不当有关？

问题分析与解答 #

1. 终止条件无问题，栈溢出源于递归深度过大 #

你的终止条件A.size() == 0是正确的，但汉诺塔的递归解法天然递归深度等于圆盘数量N。每个递归调用都会在程序栈上分配栈帧（存储参数、局部变量、返回地址等），而程序栈的默认容量有限（通常仅几MB）。当N较大时（比如几百上千），栈帧总数会超过栈的承载上限，直接触发stack-overflow错误。这和终止条件无关，是递归解法的固有局限性。

2. “递归跳跃思想”的尾递归优化无法生效 #

你提到的“递归跳跃思想”应该是指尾递归优化——即如果递归调用是函数的最后一个操作，编译器可以复用当前栈帧，避免栈内存持续消耗。但你的代码不符合尾递归要求：第一个hanota(A, C, B)调用后，还执行了C.push_back(base)和第二个hanota(B, A, C)调用，编译器无法进行栈帧复用，每一层递归都会占用新的栈空间，最终耗尽内存。

3. 代码操作的额外问题：vector头部删除效率极低 #

你用A.erase(A.begin())删除头部元素，这会导致vector中所有后续元素前移，时间复杂度为O(N)，当N较大时会带来显著性能开销。汉诺塔的柱子是栈结构，顶端应该对应vector的尾部，正确的栈操作应该用pop_back()和push_back()（O(1)时间复杂度）。

修正后的代码示例 #

基于圆盘数量递归，同时采用栈的尾部操作优化效率：

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        // 直接基于圆盘数量递归，避免每次操作容器时计算size
        move(A.size(), A, B, C);
    }

private:
    void move(int n, vector<int>& from, vector<int>& temp, vector<int>& to) {
        if (n == 0) {
            return;
        }
        // 把n-1个圆盘从from移到temp，借助to作为中转
        move(n - 1, from, to, temp);
        // 移动最底层的圆盘到目标柱子
        to.push_back(from.back());
        from.pop_back();
        // 把n-1个圆盘从temp移到to，借助from作为中转
        move(n - 1, temp, from, to);
    }
};

注意：即使修正后，当N极大时（比如上万），递归深度仍会导致栈溢出。如果要彻底避免这个问题，需要改用非递归的迭代实现，用自定义栈模拟递归过程。

内容的提问来源于stack exchange，提问作者STACK_LIFO