Рекурсивные методы всегда лучше, чем итеративные методы в Java?

Кроме того, они всегда могут использоваться вместо итерации и наоборот?

Ответы

Ответ 1

Рекурсивные методы всегда лучше, чем итеративные методы в java?

Нет

Кроме того, они всегда могут использоваться вместо итерации и наоборот?

Вы можете всегда сделать рекурсивную функцию итеративной. (если память справится с этим, см. интересную ссылку здесь)

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

Рекурсия более дорогостоящая в памяти, но иногда она более понятная и понятная. Использование циклов увеличивает производительность, но рекурсия иногда может быть лучше для программиста (и его производительности).

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

Пример

Рассмотрим эти две реализации для факториала:

Итерационный:

private int Factorial(int num)
{
    int result = 1;
    if (num <= 1) 
       return result;
    while (num > 1)
    {
        result * = num;
        num--;
    }
    return result;
}

рекурсии:

private int Factorial(int num)
{
    if (num <= 1) 
        return 1;
    return num * Factorial(num - 1);
}

Какой способ более читабельный?

Очевидно, что он рекурсивный, он прямолинейный и может быть написан и успешно запущен с первой попытки. Это просто перевод математического определения в Java!

Какой метод более эффективен?

Возьмем, например, num = 40, здесь сравнение времени:

long start = System.nanoTime();
int res = Factorial(40);
long end = System.nanoTime();
long elapsed = end - start;

System.out.println("Time: " + elapsed);

2993 для рекурсивного

2138 для итеративного

конечно, разница будет больше, если число больше.

Ответ 2

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

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

Должен ли я использовать рекурсию или итерацию?

Рекурсия обычно используется из-за того, что ее проще реализовать, и она обычно более "элегантна, чем итеративные решения". Помните, что все, что было сделано в рекурсии, также можно выполнить итеративно, но с рекурсией обычно существует недостаток производительности. Но в зависимости от проблемы, которую вы пытаетесь решить, этот недостаток производительности может быть очень незначительным - и в этом случае имеет смысл использовать рекурсию. С рекурсией вы также получаете дополнительную выгоду, которую другие программисты могут более легко понять ваш код, что всегда хорошо.

Ответ 3

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

Как выбрать: зависит от вашего языка и удобства написания рекурсивного решения.

Изменить, чтобы уточнить, что я имел в виду под "непосредственно":

Существует три типа рекурсии, основанных на том, как напрямую они могут быть преобразованы в итерацию:

Оптимизируется Tail-call, в котором самой последней операцией в методе является рекурсивный вызов. Они могут быть переведены непосредственно в цикл.
Рекурсия, которая не оптимизируется для перехвата вызовов, поскольку она требует сохранения информации между вызовами, но не нуждается в стеке. Факториал, выраженный как fact(N), является классическим примером: в рекурсивной формулировке последняя операция не является рекурсивным вызовом, а является умножением. Эти типы рекурсивных вызовов могут быть легко преобразованы в оптимизированную форму хвостового вызова, а оттуда в итеративную форму (чтобы преобразовать факториал в оптимизированную форму хвостового вызова, вы должны использовать версию с двумя аргументами fact(n, acc), где acc - накопленный результат).
Рекурсия, требующая сохранения состояния при каждом вызове. Классическим примером является обход дерева предзаказов: при каждом вызове вы должны помнить родительский node. Невозможно преобразовать это прямо в итерацию. Вместо этого вы должны создать свой собственный стек, чтобы удерживать состояние от каждого вызова.

Ответ 4

Утверждение "Рекурсия всегда лучше, чем итерация" ложна. Бывают случаи, когда один из них предпочтительнее другого.

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

Чтобы ответить на ваш второй вопрос, да, любой итерационный алгоритм может быть реализован с использованием рекурсии и наоборот.

Ответ 5

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

Здесь следует 2 примера программирования для факториала:

Iteractive:

public int calculateIteractiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    int factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial = factorial * i;
    }
    return factorial;
}

Рекурсивный:

public int calculateRecursiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    return n * calculateRecursiveFactorial(n - 1);
}

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

Ответ 6

Строго говоря, рекурсия и итерация одинаково сильны. Любое рекурсивное решение может быть реализовано как итеративное решение со стеком. Обратное преобразование может быть более сложным, но наиболее тривиальным является просто передача состояния вниз по цепочке вызовов.

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

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

void walkTree(TreeNode t) {
    doSomething(t);

    if (t.hasLeft()) { walkTree(t.getLeft()); }
    if (t.hasRight()) { walkTree(t.getRight()); }
}

по сравнению с эквивалентным итерационным решением

void walkTree(TreeNode t) {
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(t);
    while (!s.empty()) {
        TreeNode t = s.pop();
        doSomething(t);
        if (t.hasLeft()) { s.push(t.getLeft()); }
        if (t.hasRight()) { s.push(t.getRight()); }
    }
}

В итеративном случае вам придется заплатить за любой мусор, созданный объектом Stack<>. В рекурсивном случае вы будете использовать стек процесса, который не будет создавать мусор или выделять какую-либо память. Рекурсивное решение уязвимо для, но в противном случае будет работать быстрее.

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

void walkList(ListNode n) {
    doSomething(n);
    if (n.hasNext()) { walkList(n.getNext()); }
}

Так как "walkList" - это последнее, что сделано в функции, JIT преобразует его по существу в "n = n.getNext(); начало goto", что сделает его эквивалентным итеративному решению.

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

Ответ 7

Если мы помним механизм передачи по значению java, мы можем понять, что рекурсия потребляет больше памяти, поскольку для каждого вызова вы передаете копию ссылочного адреса объекта или значения некоторого примитивного типа. Так, как параметры mach, которые вы передаете для каждого рекурсивного вызова в качестве машинной памяти, которую вы будете потреблять для каждого вызова, с другой стороны, петли являются легкими в использовании. Но, конечно, мы знаем, что существуют алгоритмы "разделить и побеждать", например, Mergesort или итерации на дереве, которые потребляют меньше шагов с помощью рекурсии для получения результата. Поэтому в этих случаях я считаю, что лучше использовать рекурсию.

Ответ 8

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