Q:

How can I convert recursive function to iterative function? 

I have this recursive function to calculate the modulo:
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);
        }

}

How can I make the same function use iteration? 
This is what I have so far:
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];

}

A:

The algorithm is exponentiation by squaring.  The equations are:
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

This yields this iterative code:
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;
}

