尾递归算法转迭代通用方法及幂函数实现问题咨询

问题背景 #

在函数式编程课程中了解到尾递归调用等价于while循环，已经掌握阶乘、斐波那契的尾递归转迭代方法。现在需要将一个对数时间复杂度的尾递归幂函数转为迭代算法，要求掌握通用转换方法而非仅现成实现，同时规避语言递归限制。自己编写的迭代版本无法正常运行，希望得到修正方案。

原尾递归幂函数（初始acc=1） #

unsigned int power(unsigned int x, unsigned int n, unsigned int acc) {
    if (n == 0) {
        return acc;
    }
    else if (n % 2 == 0) {
        return power(x*x, n/2, acc);
    } 
    else {
        return power(x*x, (n-1)/2, x*acc);
    }
}

本人编写的异常迭代代码 #

long long unsigned int powerIter(long long unsigned int x, long long unsigned int n) {
    long long unsigned int acc = 1;
    long long unsigned int i = 0;
    long long unsigned int temp = 0;
    while (i < n) {
        if (i % 2 == 0) {
            x *= x;
            i /= 2;
        }
        else {
            temp = x;
            x *= x;
            i = (i-1)/2;
            acc *= temp;
        }
        i++;
    }
    return acc;
}

尾递归转迭代通用步骤 #

尾递归的核心是每次递归调用时传递当前状态（参数值），直到触发终止条件。转迭代的本质是用循环模拟状态更新过程，步骤如下：

• 明确终止条件：对应递归的基准情况（如本例中n == 0）
• 提取状态变量：递归函数的所有参数都是需要维护的状态，这里为x、n、acc
• 循环模拟递归：将递归的分支逻辑改为循环内的条件判断，每次循环直接更新状态变量
• 移除递归调用：把递归调用中的参数更新逻辑直接作用在循环内的状态变量上，无需函数调用

正确迭代实现与错误分析 #

正确代码 #

long long unsigned int powerIter(long long unsigned int x, long long unsigned int n) {
    long long unsigned int acc = 1;
    // 循环直到满足终止条件n == 0
    while (n > 0) {
        // 对应递归中n为奇数的分支：更新累积值
        if (n % 2 == 1) {
            acc *= x;
        }
        // 统一执行x平方、n折半的操作（对应递归中两种分支的共同参数更新）
        x *= x;
        n /= 2;
    }
    return acc;
}

错误原因 #

你的代码引入了多余的i变量，完全偏离了原尾递归的状态更新逻辑：原递归是通过不断缩小n的值直到为0来推进计算，而你的循环是让i从0增长到n，执行路径与原递归完全不符，导致结果错误。

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