Можно ли сказать, что везде, где используется рекурсия, можно использовать forцикл? И если рекурсия обычно медленнее, в чем техническая причина ее использования при forповторении цикла?

И если всегда можно преобразовать рекурсию в forцикл, есть ли практический способ сделать это?

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

Некоторые оптимизации, такие как оптимизация хвостового вызова , ускоряют рекурсию, но не всегда возможны и не реализованы на всех языках.

Основные причины использования рекурсии:

• что во многих случаях он более интуитивно понятен, когда имитирует наш подход к проблеме
• что некоторые структуры данных, такие как деревья, легче исследовать с помощью рекурсии (или в любом случае потребуются стеки)

Конечно, каждую рекурсию можно смоделировать как своего рода цикл: это то, что в конечном итоге будет делать ЦП. А сама рекурсия, если говорить более прямо, означает помещение вызовов функций и областей видимости в стек. Но изменение вашего рекурсивного алгоритма на циклическое может потребовать много работы и сделать ваш код менее удобным в обслуживании: как и в случае любой оптимизации, ее следует предпринимать только тогда, когда какое-либо профилирование или свидетельства показывают, что это необходимо.

Можно ли сказать, что везде, где используется рекурсия, можно использовать цикл for?

Да, потому что рекурсия в большинстве процессоров моделируется с помощью циклов и структуры данных стека.

И если рекурсия обычно медленнее, в чем техническая причина ее использования?

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

И если всегда можно преобразовать рекурсию в цикл for, существует ли практический способ сделать это?

Напишите итерационные программы для алгоритмов, которые лучше всего понять при итеративном объяснении; писать рекурсивные программы для алгоритмов, которые лучше всего объяснить рекурсивно.

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

Вопрос:

И если рекурсия обычно медленнее, то какова техническая причина ее использования для итерации цикла?

Ответ :

Потому что в некоторых алгоритмах ее сложно решить итеративно. Попробуйте решить поиск в глубину как рекурсивно, так и итеративно. Вы поймете, что решить DFS с помощью итераций просто сложно.

Еще одна хорошая вещь, которую стоит попробовать: попробуйте итеративно написать сортировку слиянием. Это займет у вас некоторое время.

Вопрос:

Можно ли сказать, что везде, где используется рекурсия, можно использовать цикл 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)); 
   }
}

В большинстве ответов предполагается, что iterative= for loop. Если ваш цикл for не ограничен ( как C, вы можете делать все, что хотите, с вашим счетчиком циклов), тогда это правильно. Если это реальный for цикл (скажем , как в Python или большинства функциональных языков , где вы не можете вручную изменить счетчик цикла), то это не правильно.

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

Гораздо важнее то, что многие функции очень легко реализовать рекурсивно и ужасно сложно реализовать итеративно (ручное управление стеком вызовов не в счет).

Да, как сказал по Thanakron Tandavas ,

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

Например: Башни Ханоя.

1. N колец увеличивающегося размера
2. 3 полюса
3. Кольца начинают складываться на шесте 1. Цель состоит в том, чтобы переместить кольца так, чтобы они располагались на шесте 3 ... Но
   • Можно перемещать только одно кольцо за раз.
   • Нельзя ставить большее кольцо поверх меньшего.
4. Итерационное решение «мощное, но уродливое»; рекурсивное решение «элегантно».

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

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

рекурсия + запоминание может привести к более эффективному решению по сравнению с чистым итеративным подходом, например, проверьте это: http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

Краткий ответ: компромисс в том, что рекурсия выполняется быстрее, а циклы занимают меньше памяти почти во всех случаях. Однако обычно есть способы изменить цикл или рекурсию for, чтобы они работали быстрее.