Что быстрее в Java, в то время как или с помощью рекурсивного метода?

Ответ 1

Рекурсия будет медленнее из-за накладных расходов на вызов метода и использования стека вызовов.

Java также не выполняет оптимизацию хвостовых вызовов, поэтому не рассчитывайте на это. (Несмотря на то, что в JVM есть языки с оптимизацией хвостовых вызовов, включая Clojure и Kotlin)

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

Если вы делаете это просто для того, чтобы попробовать что-то, я предлагаю использовать VisualVM, который можно найти в java JDK. Это профилировщик, который можно использовать для оценки ситуации такого рода (или вы можете запросить лицензию YourKit с открытым исходным кодом, если вы работаете над OSS).

Обратите внимание, что я не рекомендую использовать рекурсию только для фантазии. Используйте его, если он вам действительно нужен (например, обход деревьев).

Ответ 2

Вы должны запустить код с измерением времени. Здесь у вас есть мой вывод для 100 рекурсий /100 в циклах:

Recursive time: 90941
While time: 5180

Это ясно показывает, что while цикл быстрее, чем рекурсия.

Вы можете проверить мои измерения, запустив этот код:

public class Process {

    public Process() {
    }

    public static void countRecursive(int num) {
        num++;
        if (num <= 100) countRecursive(num);
        else return;
    }

    public static void countWhile(int num) {
        do
            num++;
        while (num <= 100);
    }

    public static void main(String[] args) {
        Long start = System.nanoTime();        
        Process.countRecursive(0);
        System.out.println("Recursive time: " + (System.nanoTime() - start));
        Long startWhile = System.nanoTime();
        Process.countWhile(0);
        System.out.println("While time: " + (System.nanoTime() - startWhile));

    }

}

Ответ 3

Я бы не предлагал использовать Recursion, так как каждая рекурсия хранится в стеке. Таким образом, вам необходимо сохранить параметры метода, локальные переменные и т.д. Для каждого рекурсивного вызова, чтобы поддерживать состояние метода до этого вызова.

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

Кроме того, вы также можете сравнить свой код, чтобы узнать, какой из них работает быстрее. Вы получите представление.

Ответ 4

Рекурсивные вызовы добавляют стеки кадров в стек вызовов. Петли не делают. Циклы, как правило, быстрее, чем рекурсия, если рекурсия не является частью алгоритма, такого как divide and conquer (который не является вашим примером).

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

Ответ 5

В общем, я предпочитаю итерацию (например, время или цикл) по рекурсии, потому что:

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

Ответ 6

В общем случае рекурсия оптимизируется, если это возможно, на петлях, что означает, что по разным причинам, в том числе распределение кадров стека и переполнение стека, превалирует над рекурсией, если эти два решения в остальном равны. См. Рекурсия хвоста
Поэтому, игнорируя тот факт, что Java не оптимизирует Tail Recursion, циклы должны быть быстрее.

Также посмотрите this

Ответ 7

В java рекурсия немного дороже по сравнению с циклом while, потому что для этого требуется выделение нового стекового кадра. Рекурсия может быть быстрее, если альтернатива заключается в явном управлении стеком

Ответ 8

То, что все остальные сказали, верно. Я хотел бы добавить еще одну вещь: для проблемы, которую вы отправили, считая от 1 до 10, использование рекурсии или итерации будет хорошо в любом случае, потому что они оба занимают незначительное количество времени для запуска. В общем, на современных компьютерных системах вам не нужно слишком беспокоиться о том, сколько времени потребуется для завершения процесса (если вы не имеете дело с большими наборами данных), потому что память настолько дешевая, и процессоры настолько мощные.

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

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