Включить рекурсивную программу для итерационных

Question

Друг предложил мне написать программу, которая получает три целых числа (int a, int n, int k) и вычисляющий как можно более эффективно, a^n mod k

Я пришел с этим решением

public static int rec(int a,int n,int k) //calc a^n mod k 
    { 
     if(n == 1) 
      return a % k; 
     int exp1 = rec(a, n/2, k), exp2 = exp1; 
     if(n % 2 == 1) 
      exp2 = rec(a, n/2 + 1, k); 

     return (exp1 * exp2) % k; 
    } 

Это невероятно простой рекурсивный решение, полагающееся на то, что a^(b+c) mod d = (a^b mod d * a^c mod d) mod d, и работает в логарифмическом времени. По крайней мере, теоретически.

На практике, когда мы измеряли наше решение, его линейное временное решение было лучше, чем мое решение. Я подозреваю, что это связано с использованием рекурсии, а не циклов. Имеет ли это смысл? Если да - как я могу превратить этот код в итеративную программу?

Answer 1

Имеет ли это значение?

Да. Как отметил Борис Паук, в Java нет оптимизации хвостов.

Как я могу превратить этот код в итеративную программу?

Позвольте мне скопировать и вставить итеративный решение рассчитать силу ряда из here

int pow(int x, int n) { 
int res = 1; 
while(n > 0) { 
    if(n % 2 == 1) { 
     res = res * x; 
    } 
    x = x * x; 
    n = n/2; 
} 
return res; 
} 

Отказ от ответственности: Хотя приведенный выше код выглядит хорошо для меня, я не проверял лично.