Рекурсия против циклов - Factorials, Java

Question

Какой из этих двух методов получения факториала (петля против рекурсии) более эффективен / быстрее? и если это можно улучшить, как так?

Язык: Java

private static long factrecur(int n) {
    if (n == 0) {
        return 1;
    }
    else {
        return n * factrecur(n-1);
    }

}

private static long factloop(int a) {
    long total = 1;
    for (int b=a;b>=1;b--) {
        total *= b;
    }
    return total;
}

Answer 1

Цикл for будет более эффективным, поскольку нет необходимости использовать вызовы метода. (Как правило, циклы почти всегда более эффективны, чем рекурсия)

Чтобы объяснить, почему вы должны вдаваться в подробности того, что происходит, когда вы вызываете метод и что-то, называемое стек вызовов .

В основном, когда вы вызываете метод, ему нужно немного места для работы (для таких вещей, как его локальные переменные и т. Д.), Ему также нужно место для входящих параметров, передаваемых ему, и место для хранения адреса возврата, где он должен идти, когда это сделано, выполняя. Это пространство динамически обеспечивается путем «помещения» значений в стек. Это пространство стека остается занятым до тех пор, пока метод не вернется, и в этот момент он «вытолкнут».

Итак, подумайте о рекурсии в этом контексте: каждый раз, когда вы вызываете метод изнутри себя, вы помещаете больше данных в стек, не возвращаясь из метода, в котором вы были (и, таким образом, не освобождая пространство стека, которое занимал вызывающий метод) ). По мере углубления вашей рекурсии количество памяти увеличивается.

В отличие от написанного вами цикла for, используется только фиксированный объем памяти, предоставляемый одним нажатием фрейма стека.

Answer 2

При 21 вызове ваша длинная воля превысит , что очень рано для измерения разницы, которая может стать релевантной.

Вам может понадобиться BigInteger для измерения значительной разницы при измерении factorial (10*1000*1000) или чего-то такого большого.Если у вас нет старших чисел для вычисления, но рассчитаны низкие факториалы часто , хэш-карта с предварительно рассчитанными значениями будет быстрее, чем рекурсия и цикл.

Answer 3

Единственная проблема с рекурсией состоит в том, что каждый раз, когда вызывается функция, ее адрес помещается в верхнюю часть стека, конкатенация большого количества вызовов может вызвать переполнение стека исключение, если число рекурсии звонки высокие.