Можно ли сказать, что везде recursion используется цикл for для использования? И если рекурсия обычно медленнее, то какая техническая причина для ее использования для повторения цикла?
И если всегда можно преобразовать рекурсию в цикл for, существует ли это правило большого пальца?
Рекурсия обычно намного медленнее, потому что все вызовы функций должны храниться в стеке, чтобы вернуться к функциям вызывающего абонента. Во многих случаях память должна быть выделена и скопирована для реализации выделения изоляции.
Некоторые оптимизации, такие как оптимизация хвостового вызова, делают рекурсии быстрее, но не всегда возможны и не реализованы на всех языках.
Основными причинами использования рекурсии являются
Конечно, каждая рекурсия может быть смоделирована как своего рода цикл: это то, что в конечном итоге сделает процессор. И сама рекурсия, более прямо, означает помещение вызовов функций и областей в стек. Но изменение вашего рекурсивного алгоритма на цикл может потребовать много работы и сделать ваш код менее ремонтопригодным: как и для каждой оптимизации, его следует делать только тогда, когда некоторые профилирования или доказательства показали, что это необходимо.
Правильно ли говорить, что везде, где используется рекурсия, может использоваться цикл for?
Да, поскольку рекурсия в большинстве процессоров моделируется с помощью циклов и структуры данных стека.
И если рекурсия обычно медленнее, то какова техническая причина ее использования?
Это не "обычно медленнее": это рекурсия, которая применяется неправильно, что медленнее. Кроме того, современные компиляторы умеют конвертировать некоторые рекурсии в циклы, даже не спрашивая.
И если всегда можно преобразовать рекурсию в цикл for, существует ли это правило большого пальца?
Напишите итеративные программы для наиболее понятных алгоритмов, когда они объясняются итеративно; записывать рекурсивные программы для алгоритмов, наилучшим образом объясняемые рекурсивно.
Например, поиск двоичных деревьев, выполнение quicksort и разбор выражений во многих языках программирования часто объясняется рекурсивно. Они также лучше всего кодируются рекурсивно. С другой стороны, вычисление факториалов и вычисление чисел Фибоначчи гораздо легче объяснить с точки зрения итераций. Использование рекурсии для них похоже на спутывание мух с кувалдой: это не очень хорошая идея, даже когда кувалда действительно делает хорошую работу в ней +.
И если рекурсия обычно медленнее, то какая техническая причина когда-либо использовать ее для повторения цикла?
Потому что в некоторых алгоритмах их сложно решить итеративно. Попробуйте разрешить поиск по глубине как рекурсивно, так и итеративно. Вы поймете, что трудно решить DFS с итерацией.
Еще одна хорошая вещь: попробуйте написать Merge sort iteratively. Это займет у вас довольно много времени.
Правильно ли говорить, что везде, где используется рекурсия, может использоваться цикл for?
Да. Этот поток имеет очень хороший ответ для этого.
И если всегда можно преобразовать рекурсию в цикл for, существует ли это правило большого пальца?
Поверь мне. Попробуйте написать свою версию, чтобы разрешить поиск по глубине итеративно. Вы заметите, что некоторые проблемы проще решить рекурсивно.
Подсказка: рекурсия хороша, когда вы решаете проблему, которая может быть решена с помощью делить и побеждать.
Помимо замедления, рекурсия может также приводить к ошибкам в зависимости от того, насколько глубоко она проходит.
Чтобы написать эквивалентный метод с использованием итерации, мы должны явно использовать стек. Тот факт, что итеративная версия требует наличия стека для его решения, указывает на то, что проблема достаточно сложная, и она может выиграть от рекурсии. Как правило, рекурсия наиболее подходит для проблем, которые не могут быть решены с фиксированным объемом памяти и, следовательно, требуют стека, когда они решаются итеративно. Сказав это, рекурсия и итерация могут показать один и тот же результат, в то время как они следуют разной схеме. Чтобы решить, какой метод работает лучше, в каждом случае лучше всего выбирать на основе шаблона, который следует за этой проблемой.
Например, чтобы найти n-е треугольное число Треугольная последовательность: 1 3 6 10 15... Программа, использующая итеративный алгоритм для поиска n-го треугольного числа:
Использование итеративного алгоритма:
//Triangular.java
import java.util.*;
class Triangular {
public static int iterativeTriangular(int n) {
int sum = 0;
for (int i = 1; i <= n; i ++)
sum += i;
return sum;
}
public static void main(String args[]) {
Scanner stdin = new Scanner(System.in);
System.out.print("Please enter a number: ");
int n = stdin.nextInt();
System.out.println("The " + n + "-th triangular number is: " +
iterativeTriangular(n));
}
}//enter code here
Использование рекурсивного алгоритма:
//Triangular.java
import java.util.*;
class Triangular {
public static int recursiveTriangular(int n) {
if (n == 1)
return 1;
return recursiveTriangular(n-1) + n;
}
public static void main(String args[]) {
Scanner stdin = new Scanner(System.in);
System.out.print("Please enter a number: ");
int n = stdin.nextInt();
System.out.println("The " + n + "-th triangular number is: " +
recursiveTriangular(n));
}
}
Кажется, я помню, как мой профессор компьютерных наук сказал в тот день, что все проблемы с рекурсивными решениями также имеют итеративные решения. Он говорит, что рекурсивное решение обычно медленнее, но они часто используются, когда их легче рассуждать и кодировать, чем итеративные решения.
Однако, в случае более продвинутых рекурсивных решений, я не считаю, что он всегда сможет реализовать их, используя простой цикл for.
Большинство ответов, по-видимому, предполагают, что iterative= for loop. Если ваш цикл for не ограничен (a la C, вы можете делать все, что хотите, с помощью счетчика циклов), то это верно. Если это реальный цикл for (скажем, как на Python или на большинстве функциональных языков, где вы не можете вручную изменить счетчик циклов), тогда он не правильный.
Все (вычислимые) функции могут быть реализованы как рекурсивно, так и с использованием циклов while (или условных переходов, которые в основном одинаковы). Если вы действительно ограничиваете себя for loops, вы получите только подмножество этих функций (примитивно-рекурсивные, если ваши элементарные операции являются разумными). Конечно, это довольно большое подмножество, которое, случается, содержит каждую отдельную функцию, которую вы, вероятно, получите на практике.
Что гораздо важнее, так это то, что многие функции очень легко реализовать рекурсивно и ужасно сложно реализовать итеративно (ручное управление стеком вызовов не учитывается).
Рекурсия медленнее по сравнению с итерацией, как указано в приведенных выше ответах, однако рекурсия подходит в определенных сценариях, и итеративный подход хорош для определенных сценариев. Однако, прежде чем выбирать рекурсию, лучше проанализировать, какую проблему вы собираетесь решить. Самое главное - дать большой вклад в анализ. Я надеюсь, что приведенная ниже ссылка даст вам больше ясности, http://knowledge-cess.com/recursion-vs-iteration-an-analysis-fibonacci-and-factorial/
Да, как сказал Thanakron Tandavas,
Рекурсия хороша, когда вы решаете проблему, которая может быть решена методом деления и покорения.
Например: Башни Ханоя
рекурсия + запоминание может привести к более эффективному решению сравнить с чистым итерационным подходом, например. Проверь это: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n
Короткий ответ: компромисс - это рекурсия быстрее, и для циклов в большинстве случаев требуется меньше памяти. Однако обычно есть способы изменить цикл for или рекурсию, чтобы ускорить ее выполнение.