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

Question

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

Answer 1

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

ссылка

Answer 2

Рекурсия означает, что функция вызывает несколько раз

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

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

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

Answer 3

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

Некоторые алгоритмы (например, функция Аккермана ) не могут (легко) быть определены итеративно.

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

Answer 4

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

Почему не для использования рекурсии

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

Почему до используют рекурсию

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

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

Answer 5

Для начала:

Плюсы:

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

Минусы:

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

Answer 6

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

Answer 7

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

• , когда мы не знаем конечное число итераций, например, наше условие выхода из функции fuction основано на динамическом программировании (запоминании)
• когда нам нужно выполнить операции в обратном порядке элементов.Это означает, что мы хотим сначала обработать последний элемент, а затем 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);
}

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

Answer 8

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

Answer 9

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

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

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

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

Performance

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