关于用栈将递归（尾/非尾）转为迭代方法的技术疑问

一、非尾递归sigma1的正确转换分析 #

原递归函数sigma1是计算1到n的累加和，属于非尾递归——因为递归调用后还要执行n + ...的运算，得等递归调用完成才能算出最终结果，所以必须用栈保存待处理的数值，回溯的时候完成累加。

先看你给的两个版本的问题：

• 版本1的错误：
  1. 累加时用了res += n，但n是初始输入值，不是当前弹出的栈元素，应该改成res += elm
  2. 压栈时用push(s, n-1)也不对，得基于当前弹出的elm压入elm-1
• 版本2的错误：
  1. 逻辑完全混乱，先循环把n递减压栈，栈里会是n, n-1, ..., 0，进入else分支后第一个弹出的就是0，直接返回res（此时res还是0），根本没做累加
  2. 就算走到累加步骤，res += n里的n已经是0了，完全没有意义

正确的非尾递归转迭代版本可以这么写：

int sigma1_iter(int n) {
    stack* s = create_stack(n);
    // 先把所有要处理的数值压栈，模拟递归调用的过程
    while (n > 0) {
        push(s, n);
        n--;
    }
    int res = 0;
    // 弹出元素并累加，模拟递归回溯的过程
    while (!is_empty(s)) {
        int elm = pop(s);
        res += elm;
    }
    return res;
}

另一种更贴近真实调用栈执行流程的写法（还原递归调用时的上下文保存逻辑）：

int sigma1_iter(int n) {
    stack* s = create_stack(n);
    push(s, n);
    int res = 0;
    while (!is_empty(s)) {
        int elm = pop(s);
        if (elm == 0) {
            // 触发递归终止条件，开始回溯
            continue;
        }
        // 先压入elm-1，模拟调用sigma1(elm-1)
        push(s, elm - 1);
        // 再压入当前elm，等递归返回后再累加
        push(s, elm);
    }
    return res;
}

二、尾递归sigma2的转换 #

尾递归sigma2的核心特点是：递归调用是函数的最后一步，没有后续运算——递归调用的结果直接作为当前函数的返回值，不需要保存当前函数的上下文。所以尾递归转迭代根本不需要栈，直接用循环更新参数就行：

int sigma2_iter(int n, int res) {
    while (n != 0) {
        // 直接更新参数，模拟尾递归的调用过程
        int temp = n;
        n = n - 1;
        res = res + temp;
    }
    return res;
}

如果非要用栈（比如用来理解栈的作用），可以把每一步的n和res打包成结构体压栈，但这完全是多此一举，因为尾递归的迭代优化本来就不需要栈。硬要写的话示例如下：

// 定义栈存储的帧结构
typedef struct {
    int n;
    int res;
} Frame;

int sigma2_iter_stack(int n, int res) {
    stack* s = create_stack(n);
    Frame frame = {n, res};
    push(s, frame); // 假设栈支持存储Frame类型
    while (!is_empty(s)) {
        Frame curr = pop(s);
        if (curr.n == 0) {
            return curr.res;
        }
        // 压入下一次递归调用的参数帧
        Frame next = {curr.n - 1, curr.res + curr.n};
        push(s, next);
    }
    return res; // 不会执行到这里
}

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