c - 如何将递归函数转换为迭代函数？

Question

我有这个递归函数来计算模数：

uint64_t fast_power(uint64_t k, uint64_t n, uint32_t m) {

        uint64_t sum;
        if (n == 0) {
            return 1;
        }

        if ((n % 2) == 0) {
            sum = fast_power(k, (n / 2), m) * fast_power(k, (n / 2), m);

            return MOD(sum, m);
        } else {
            sum = k * (fast_power(k, (n - 1), m));
            return MOD(sum, m);
        }

}

如何使相同的函数使用迭代？这是我到目前为止所拥有的：

uint64_t iter_power(uint64_t k, uint64_t n, uint32_t m) {

    uint64_t arr[n - 1];

    uint64_t num;

    for (int i = 1; i < n; i++) {

        num = power(k, i);

        arr[num] = MOD(arr[num], m);

    }
    return arr[num];

}

Answer 1

该算法是通过平方取幂。方程是：

iter_pow(k, n) = iter_pow(k * k, n / 2) * k   if n % 2 == 1
iter_pow(k, n) = iter_pow(k * k, n / 2)       if n % 2 == 0

这产生了这个迭代代码：

uint64_t iter_power(uint64_t k, uint64_t n, uint32_t m) {
    uint64_t result = 1;
    while (n) {
        if (n % 2) result = MOD(result * k, m);
        n /= 2;
        k = MOD(k * k, m);
    }
    return result;
}