Каковы преимущества и недостатки рекурсии?

Ответ 1

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

ссылка

Ответ 2

Рекурсия означает повторную вызов функции

Он использует системный стек для выполнения этой задачи. Поскольку стек использует подход LIFO и когда функция называется управляемой, она перемещается туда, где определена функция, которая хранится в памяти с некоторым адресом, этот адрес хранится в стеке

Во-вторых, это уменьшает временную сложность программы.

Хотя бит не по теме, немного связан. Должен прочитать.: Рекурсия против итерации

Ответ 3

Все алгоритмы могут быть определены рекурсивно. Это значительно облегчает визуализацию и доказательство.

Некоторые алгоритмы (например, Ackermann Function) не могут (легко) быть указаны итеративно.

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

Ответ 4

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

Ответ 5

Чтобы начать:

Плюсы:

• Это единственный способ реализовать переменное число вложенных циклов (и единственный изящный способ реализации большого постоянного числа вложенных циклов).

Минусы:

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

Ответ 6

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

Почему бы не использовать рекурсию

• Это обычно медленнее из-за накладных расходов на поддержание стека.
• Обычно для стека используется больше памяти.

Зачем использовать рекурсию

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

Например, проблему Башни Ханоя легче решать с помощью рекурсии, а не итерации.

Ответ 7

выразительность

Большинство проблем естественно выражается рекурсией, такой как Fibonacci, сортировка слияний и быстрая сортировка. В этом отношении код написан для людей, а не для машин.

Неизменность

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

Производительность

Рекурсия не совместима со стеклом. Stack может переполняться, когда рекурсия плохо разработана или оптимизация хвоста не поддерживается.

Ответ 8

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

Ответ 9

Мы должны использовать рекурсию в следующих сценариях:

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

Рекурсия спасет несколько обходов. И это будет полезно, если мы сможем разделить распределение стека следующим образом:

int N = 10;
int output = process(N) + process(N/2);
public void process(int n) {
    if (n==N/2 + 1 || n==1) {
       return 1;
    }

    return process(n-1) + process(n-2);
}

В этом случае только половина стеков будет выделено в любой момент времени.