递归的本质是函数调用栈的不断压栈和出栈过程，每一次递归调用都会将当前函数的上下文信息存入系统栈，直到触发终止条件后再逐层返回。我们可以用自定义的堆栈Stack来手动维护这些上下文，从而替代系统栈完成递归逻辑的模拟，避免递归过深导致的栈溢出问题。
递归与堆栈的底层关联
系统在执行递归函数时，会自动维护一个调用栈，每次递归调用都会将当前函数的参数、返回地址、局部变量等信息压入栈中，当递归终止条件满足时，再从栈顶取出信息返回上一层执行。我们手动实现的堆栈模拟递归，本质就是复刻这个压栈和出栈的过程，把原本系统自动完成的工作转为代码手动控制。
用Stack模拟递归的核心思路
模拟递归的核心是将递归函数的每一次调用状态封装成结构体，存入自定义堆栈中，然后通过循环不断处理栈顶状态，直到栈为空。具体步骤如下：
- 定义状态结构体，存储递归函数的参数、当前执行阶段等信息
- 将初始递归调用的状态压入堆栈
- 循环处理堆栈：取出栈顶状态，根据当前阶段执行对应逻辑，若需要递归调用则生成新的状态压入栈，若满足终止条件则处理返回逻辑
- 直到堆栈为空，整个模拟过程结束
实例演示：用Stack模拟阶乘递归
以计算n的阶乘为例，原本的递归实现如下：
// 递归计算阶乘
int factorial_recursive(int n) {
if (n == 1) {
return 1;
}
return n * factorial_recursive(n - 1);
}
接下来我们用自定义堆栈模拟这个递归过程，首先定义状态结构体：
#include <stack>
#include <iostream>
using namespace std;
// 定义递归状态结构体，存储当前n值和阶段标识
// phase为0表示需要继续递归，为1表示已经获取到子递归的结果，可以计算当前结果
struct RecursionState {
int n;
int phase;
int sub_result; // 存储子递归的结果
RecursionState(int num, int p) : n(num), phase(p), sub_result(0) {}
};
然后实现非递归的阶乘计算函数：
int factorial_stack(int n) {
stack<RecursionState> st;
// 初始状态压栈
st.push(RecursionState(n, 0));
int result = 0;
while (!st.empty()) {
RecursionState &cur = st.top();
if (cur.n == 1) {
// 终止条件，直接返回1
cur.sub_result = 1;
st.pop();
if (!st.empty()) {
st.top().sub_result = cur.sub_result;
} else {
result = cur.sub_result;
}
continue;
}
if (cur.phase == 0) {
// 阶段0：需要调用子递归，压入n-1的状态
st.push(RecursionState(cur.n - 1, 0));
cur.phase = 1; // 切换到阶段1，等待子递归结果
} else if (cur.phase == 1) {
// 阶段1：已经拿到子递归结果，计算当前结果
cur.sub_result = cur.n * cur.sub_result;
st.pop();
if (!st.empty()) {
st.top().sub_result = cur.sub_result;
} else {
result = cur.sub_result;
}
}
}
return result;
}
测试代码和输出结果：
int main() {
int n = 5;
cout << "递归计算结果：" << factorial_recursive(n) << endl;
cout << "堆栈模拟计算结果：" << factorial_stack(n) << endl;
return 0;
}
// 输出：
// 递归计算结果：120
// 堆栈模拟计算结果：120
二叉树前序遍历的递归模拟
再来看一个更复杂的场景，二叉树前序遍历的递归实现如下：
// 二叉树节点定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 递归前序遍历
void preorder_recursive(TreeNode *root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorder_recursive(root->left);
preorder_recursive(root->right);
}
用堆栈模拟前序遍历的递归过程：
void preorder_stack(TreeNode *root) {
if (root == nullptr) {
return;
}
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
cout << cur->val << " ";
// 先压右子树，再压左子树，保证左子树先出栈
if (cur->right != nullptr) {
st.push(cur->right);
}
if (cur->left != nullptr) {
st.push(cur->left);
}
}
}
这个例子中，我们利用了前序遍历先访问根节点，再访问左子树，最后访问右子树的特性，用堆栈存储待访问的节点，避免了递归调用，同样能得到正确的遍历结果。
注意事项
用堆栈模拟递归时需要注意几个问题：首先要准确封装递归状态，尤其是需要记录递归执行阶段的场景，避免逻辑混乱；其次要正确处理返回值的传递，保证子递归的结果能正确传递到父调用层；最后要注意堆栈的空判断，避免出现非法访问的问题。对于简单的递归场景，非递归实现可能代码更长，但在递归深度较大时，能有效避免栈溢出，提升程序的稳定性。