Как преобразовать рекурсивную функцию в итеративную функцию?

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; 
}