В чем разница между iteration и recursion и почему/когда лучше:
while (true) {
// Iterating
}
и
private void recursion() {
if (true)
recursion(); // Recursing
return;
}
Я вижу много реализации recursive, в то время как его можно легко выполнить в простом цикле.
Существуют два основных различия между рекурсией и итерационной версией того же алгоритма.
Прежде всего, несколько раз лучше понимать рекурсивный алгоритм, чем итеративный (по крайней мере, если вы опытный программист). Это повышает выразительность и, в некоторых случаях, читаемость (это также может привести к полной противоположности в других случаях)
Expresivity - это огромная работа на языках программирования и возможность писать один и тот же код в 5 строках вместо 20 - это огромная сделка.
С другой стороны, это снижает производительность вашего кода. Рекурсивные функции должны содержать записи функций в памяти и переходить с одного адреса памяти на другой, чтобы вызывать параметры и возвращаемые значения. Это делает их очень плохими.
Сумма:
Итерационные алгоритмы = Быстрая производительность, но трудно писать (иногда трудно читать)
Рекурсивные алгоритмы = Быстрая запись, но плохая производительность (иногда легче понять)
Возьмем этот пример:
public static long fib(long n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
против
if ((n == 1) || (n == 2)) {
return 1;
} else {
long prev = 1, current = 1, next = 0;
for (long i = 3; i <= n; i++) {
next = prev + current;
prev = current;
current = next;
}
return next;
}
Источник:
http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java
Основное различие между рекурсией и итерацией - использование памяти.
Для каждого рекурсивного вызова требуется пространство на фрейме стека, что приводит к издержкам памяти.
Позвольте мне привести вам пример. Представьте себе, что в одном случае вы забыли написать базовый случай для вашей рекурсивной функции, что привело к бесконечным рекурсивным вызовам, а в другом случае вы написали бесконечный цикл.
Так как каждая рекурсивная функция назначает новое пространство памяти, в первом случае ваш код даст исключение, но во втором случае он будет продолжать работать навсегда.
Поэтому лучше сделать ваш итеративный код более понятным, чем использование рекурсии.
Это разные способы сделать то же самое. Все рекурсивные реализации могут выполняться с помощью (или нескольких) циклов (ов) и наоборот. Это больше о логике, которая стоит за ней, о том, как думать об этом. Факториал, хотя и не самый лучший пример, n * (n-1)!, поэтому имеет смысл использовать его рекурсивно.
Рекурсия и итерация - это разные способы думать о решении. Было бы глупо объяснить глубину разницы в полном объеме. В вашем примере кода вы продемонстрировали разницу. Рекурсивная функция - это тот, который вызывает себя, в то время как итеративный - это тот, который проходит через некоторый блок кода. Вот несколько статей, которые помогут вам лучше понять их: Рекурсия wiki
В теории вы всегда можете переключаться между итерацией и рекурсией. Однако, по крайней мере, в случае C/С++/С#/Java, компилятор предлагает вам некоторую поддержку, которая может сделать решение более элегантным, особенно если вы не знаете числа циклов раньше.
Лучший пример - перечисление всех файлов внутри папки и потомков. Если есть несколько подпапок, содержащих подпапки, в режиме итерации вам нужен стек, чтобы сохранить все папки, которые вам нужно проанализировать. В случае рекурсивного подхода стек уже предоставляется компилятором, и решение более элегантно.
Их можно использовать взаимозаменяемыми для решения различных проблем. В сущности, вы можете писать рекурсивные функции итеративно и наоборот.
Итерация может увеличить производительность вашей программы. В то время как рекурсия может дать более интуитивный и элегантный результат. Вы можете выбрать любой из них по вашему желанию!
Рекурсивные функции работают через процесс вызова себя до тех пор, пока условие не будет выполнено, тогда как итерация использует структуру управления циклом (например, while, do while, for), чтобы повторить раздел кода до тех пор, пока не будет выполнено определенное условие.
Рекурсивный пример:
int rec_func(int u, int k) {
if (k == 0)
return u;
return rec_func(u * k, k - 1);
}
Пример итерации:
int ite_func(int u, int k) {
while (k != 0) {
u = u * k;
k = k - 1;
}
return u;
}
Единственная реальная разница между ИМО между ними - различия в компиляции.
Рекурсия
Итерация
Данные взяты из здесь.