Превратить рекурсивную программу в итеративную

Друг предложил мне написать программу, которая получает три целых числа (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 работает в логарифмическом времени. По крайней мере теоретически.

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


java recursion exponent modular-arithmetic
person Oria Gruber    schedule 08.02.2017    source источник
comment
Рекурсия Java медленная. В Java нет оптимизации хвостовой рекурсии. Избегайте как чумы, если вам нужна производительность.   -  person Boris the Spider    schedule 08.02.2017

Ответы (1)


arrow_upward
1
arrow_downward

Имеет ли это смысл?

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

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

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

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

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

person opensam    schedule 08.02.2017