No Image

Чем отличается цикл от рекурсии

СОДЕРЖАНИЕ
3 просмотров
10 марта 2020

В настоящее время я работаю в PHP, поэтому этот пример будет в PHP, но вопрос относится к нескольким языкам.

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

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

Я собираюсь сделать упрощенную версию обоих, я надеюсь, что кто-то может объяснить, как один отличается от другого.

Пожалуйста, простите меня за любые ошибки кодирования.

Теперь приведенный выше код просто просто распечатывает номера.

Теперь сделаем это с рекурсией:

Этот метод выше будет делать то же самое, что и цикл, но только с рекурсией.

Может ли кто-нибудь объяснить мне, что в нем используется один из этих методов.

9 ответов

12 Решение augustss [2010-06-21 13:30:00]

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

Рекурсии более мощные в том смысле, что для перевода рекурсии в цикл может потребоваться стек, который вы должны манипулировать собой. (Попробуйте пересечь двоичное дерево, используя цикл, и вы почувствуете боль.)

С другой стороны, многие языки (и реализации), например Java, не реализуют хвостовую рекурсию должным образом. Рекурсия хвоста — это когда последнее, что вы делаете в функции, — это называть себя (как в вашем примере). Такая рекурсия не должна потреблять какой-либо стек, но на многих языках, что означает, что вы не всегда можете использовать рекурсию.

8 xtofl [2010-06-21 13:41:00]

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

Эти структуры данных носят конечный характер, поэтому большая часть времени их обработки более ясна с рекурсией.

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

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

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

Я не уверен, что это применимо к интерпретируемому языку, например PHP, возможно, что интерпретатор может справиться с этим лучше.

2 cHao [2010-06-21 13:36:00]

Рекурсия немного медленнее (поскольку вызовы функций медленнее, чем установка переменной), и использует больше места для стеков вызовов большинства языков. Если вы попытались printnumbers(1, 1000000000) , рекурсивная версия, скорее всего, произвела бы фатальную ошибку PHP или даже ошибку 500.

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

Читайте также:  Устройство подавления акустической обратной связи

Цикл будет быстрее, потому что при выполнении дополнительного вызова функции всегда накладные расходы.

Проблема с изучением рекурсии — это много примеров (например, факториалов) — плохие примеры использования рекурсии.

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

1 Mau [2010-06-21 13:30:00]

Ну, я не знаю о PHP, но большинство языков генерирует вызов функции (на уровне машины) для каждой рекурсии. Таким образом, у них есть потенциал для использования большого количества пространства стека, если только компилятор не выполняет оптимизацию хвостового вызова (если это позволяет ваш код). В этом смысле петли более "эффективны", потому что они не увеличивают стек. Преимущество рекурсии состоит в том, что она может выражать некоторые задачи более естественным образом.

В этом конкретном случае, с концептуальной (а не реалистической) точки зрения, эти два решения полностью эквивалентны.

И нет, я не имею в виду сайт или что-то еще. Я ЗНАЧУ "переполнение стека".

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

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

Вам не нужна рекурсия для такой плоской структуры. В первом коде, который я когда-либо использовал, рекурсия включала управление физическими контейнерами. Каждый контейнер может содержать материал (список из них, каждый с весами) и/или больше контейнеров, которые имеют вес. Мне нужен общий вес контейнера и все, что он держал. (Я использовал его, чтобы предсказать вес больших рюкзаков, полный снаряжения для кемпинга, без упаковки и взвешивания.) Это было легко сделать с рекурсией и было бы намного сложнее с петлями. Но многие проблемы, которые, естественно, подходят для одного подхода, также могут быть решены с другой.

Серия контента:

Этот контент является частью # из серии # статей: Комментарий

Этот контент является частью серии: Комментарий

Следите за выходом новых статей этой серии.

Написание кода с оптимальной производительностью

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

Рекурсия

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

  • Головная рекурсия— рекурсивный вызов выполняется ближе к началу метода и является одним из первых обрабатываемых объектов. Поскольку он вызывает сам себя, ему приходится полагаться на результаты предыдущей операции, помещенной в стек вызовов. Из-за использования стека вызовов существует вероятность переполнения стека, если стек вызовов недостаточно велик.
  • Концевая рекурсия— рекурсивный вызов выполняется в конце и является последней строкой обрабатываемого кода. Этот метод не использует стек вызовов независимо от глубины рекурсии.
Читайте также:  Node js или java

В математике рекурсия распространена достаточно широко, поэтому проще будет объяснить ее на примере рекурсивного вызова. Выражение 5! (факториал числа 5) можно записать следующим способом:

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

В листинге 1 приведен пример вычисления 5! с помощью головной рекурсии.

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

В листинге 1 приведен пример вычисления 5! с помощью головной рекурсии.

Листинг 1. Листинг 1

Каждый рекурсивный вызов должен быть завершен и помещен в стек вызовов до расчета факториала. Java™ будет интерпретировать каждый вызов метода getFactorial следующим образом (каждая строка представляет объект, находящийся в стеке вызовов):

5 * getFactorial(4)
5 * (4 * getFactorial(3))
5 * (4 * (3 * getFactorial(2)))
5 * (4 * (3 * (2 * getFactorial(1))))
5 * (4 * (3 * (2 * 1)))
120

В листинге 2 приведен пример вычисления 5! с помощью концевой рекурсии.

Листинг 2. Листинг 2

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

Листинг 3. Листинг 3

Языки программирования предоставляют циклы нескольких разных типов, очень хорошо знакомых большинству программистов. В языке программирования Java имеются циклы for, do и while. Цикл — это многократное исполнение нескольких операторов. Циклы не заносят данные в стек вызовов независимо от числа исполнений цикла. Важным отличием циклов от рекурсивных функций является тот факт, что циклы используют для подсчета числа исполнений итератор, а рекурсивные функции для определения момента выхода должны выполнять сравнение результатов. Другим важным отличием является возможность применения в циклах фильтров и прочих селекторов. Примером такой ситуации может служить цикл foreach.

Что лучше?

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

Контрольные примеры

Приведенные ниже контрольные примеры запускались в 64-разрядной среде исполнения IBM Java Runtime Environment (JRE) 7.0.4.0 (с аргументом командной строки -Xms256m -Xmx256m -Dcom.ibm.tools.attach.enable=no). Чтобы среда исполнения не тратила время на расширение и сжатие кучи, JRE запускалась с фиксированным размером кучи 256 МБ. Отключение API Attach не позволяет JRE запускать приложения-агенты (обычно используемые для мониторинга), что нормализует производительность в каждом тесте. При увеличении стека вызовов для инициализации стека и поддержания его на уровне 3 МБ использовался аргумент командной строки -Xss3m -Xssi3m.

Вычисление суммы

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

Рисунок 1. Рисунок 1. Вычисление суммы

Вычисление факториала

Этот примечательный пример иллюстрирует зависимость результатов от используемых операторов. При использовании простого типа данных int лучшие результаты во всех случаях получились для цикла. Применение типа int ограничивает величину результата до 32-разрядного целого числа со знаком. Для больших факториалов можно использовать тип данных BigInteger, но такая конструкция будет более затратной. Результаты применения BigInteger показали, что использование головной рекурсии в паре с концевой обеспечивает лучшее быстродействие, чем чисто концевая рекурсия или цикл.

Рисунок 2. Рисунок 2. Вычисление факториала

Области применения рекурсии

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

Читайте также:  256Gb ssd plextor s3c px 256s3c

В задаче, получившей название Ханойская башня, даны три стрежня и диски разного размера, которые в исходном состоянии надеты на первый стержень в виде башни. Задача состоит в том, чтобы перенести башню на другой стержень, при этом запрещается класть большой диск на маленький. Эту замечательную задачу можно легко решить с помощью рекурсии за 2n — 1 ходов, где n — число дисков.

Например, возьмем четыре диска и попытаемся перенести их со стержня A на стержень C, используя стержень B для временного хранения. С помощью описанной ниже рекурсивной функции это может быть выполнено за 15 ходов. Процесс решения можно визуализировать этим апплетом. Функция вызывается (2n * 2) – 1, или 31 раз. Причина, по которой число вызовов функции не равно числу ходов, кроется в том, что для обработки ходов необходимо установить стек вызовов. В этом примере используется головная рекурсия (листинг 4).

Листинг 4. Листинг 4

Результат для четырех дисков показан в листинге 5.

Листинг 5. Листинг 5

Ханойская башня — широко распространённая задача, которую можно решить с помощью рекурсии. Однако не все задачи столь очевидны, многие из них требуют времени на анализ и решение. Ханойскую башню можно решить и с помощью циклов, однако это потребует использования нескольких различных циклов и итераторов. Это решение будет работать дольше и потребует большего объема кода.

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

Листинг 6. Листинг 6

Заключение

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

С точки зрения теории вычислительных процессов программа с рекурсией может быть заменена эквивалентной программой с циклами.

Какая альтернатива предпочтительна в программировании?

Что проще писать, читать, поддерживать?

Чтобы не уводить тему в сторону эффективности кода, предположим, что задача не глубокая по сравнению с размером стека. Или компилятор поддерживает хвостовую рекурсию.

  • Вопрос задан более трёх лет назад
  • 16888 просмотров

Все зависит от задачки. Порою достаточно простого цикла, с ним и работать проще и нет проблем со стеком. Еще, лучше все таки в цикле решать задачи, где результат следующего полностью зависит от результата предыдущего (например, факториал).

При других задачках (например, обход вложенных каталогов), когда при этом у каждого имеется ряд своих отдельных переменных (например, количество файлов в данном каталоге), или асинхронных потоков, то поддерживать легче будет рекурсию. Да и рекурсия в данном случае будет удобнее, потому что обход одного каталога совсем не зависит от результатов обхода другого соседнего каталога, и они могут работать параллельно, независимо друг от друга. А затем в конце просто объединяют все свои результаты.

Еще рекурсия будет эффективна, если рекурсивная функция кешируемая, например, она запоминает результат и при следующем запросе просто возвращается кешированный вариант.

Комментировать
3 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector