Цикл и рекурсия отличия

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

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

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

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

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

теперь код выше просто распечатывает цифры.

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

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

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

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

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

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

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

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

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

Рекурсия

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

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

В математике рекурсия распространена достаточно широко, поэтому проще будет объяснить ее на примере рекурсивного вызова. Выражение 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. Вычисление факториала

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

  1. Что такое цикл?
  2. Что такое рекурсия?
  3. Практические примеры каждого метода
  4. В каких случаях применять тот или иной метод
  5. Как выглядит рекурсивная структура данных

Начнём с метода, который кажется более простым из этих двух.

Циклы for

Цикл for используют для перебора последовательности данных (списка, кортежа, словаря, набора или строки). При достижении конца последовательности цикл завершается.

Читайте также:  Как контролировать трафик на андроиде

Например, вам нужно сложить числа от 1 до 5 и получить их сумму. Конечно, вы можете просто суммировать 1+2+3+4+5. Но, создать функцию намного удобнее, потому что вы сможете использовать её повторно, причём подставляя любые значения, даже если они не известны заранее.

Это будет выглядеть примерно так:

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

Вот как это выглядит в коде:

В начале, функция принимает число в качестве параметра. Возьмём число 5 для примера. Далее мы создаём переменную для хранения результата и устанавливаем её значение на 0. После этого начинаем перебирать список чисел от 0 до n+1 . Мы должны указать именно n+1 , потому что иначе выражение list(range(n)) не будет включать n , т.е. будет суммировать 0,1,2,3,4.

Запустив код, мы увидим, что все числа на своих местах и нам возвращается их сумма.

Вывод функции:

Рекурсия

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

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

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

Вот как это выглядит в коде:

Как видите мы передаём два значения: начальное и итоговое. При первом вызове функции итоговое значение равно 0, а начальное 5. Мы проверяем, является ли начальное число 0. Если нет, то вызываем функцию снова, но на этот раз мы меняем входное значение на 5–1 и 0+5, и повторяем этот процесс до тех пор, пока n не будет равно 0. После выполнения этого условия мы возвращаем итоговое значение (15).

Вычисление сложного процента рекурсией и циклом FOR

Давайте разберём более сложную задачу. Нужно определить стоимость кредита или инвестиции со сложным процентом. Чтобы это сделать, нам нужны следующие данные:

  1. Срок кредита в годах
  2. Процентная ставка
  3. Количество платежей в год
  4. Сумма кредита

Формула расчёта сложного процента:

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

Давайте сразу создадим переменные, в которых будем хранить исходные числа и используем их в обоих методах:

Расчёт по сложной процентной ставке итеративно

Давайте сразу посчитаем общее количество платежей, чтобы упростить вычисление в цикле. Так как платежи ежемесячные, а количество лет равно 10, то результат будет 120, или 10*12. Теперь мы можем вычислять процент для каждого месяца и добавлять результат каждой итерации к основной сумме.

Так выглядит код:

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

Результат наших вычислений:

Расчёт по сложной процентной ставке рекурсивным способом

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

  • Условие 1: Счётчик не равен 0.

Выполнить вычисление сложного процента. Добавить результат вычисления к общей сумме. Уменьшить значение счётчика на 1. Повторить те же действия, подставив новое значения для счётчика и общей суммы.

  • Условие 2: Счётчик равен 0

Возврат общей суммы

В предыдущем примере, цикл функции начинался со значения 5 и завершался при 0.

Здесь происходит тоже самое, только начальное значение теперь 120

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

Когда использовать рекурсию

Выбор между рекурсивным и итеративным методом может в значительной степени зависеть от языка, который вы используете, или от задачи, которую вы намерены решить. Например, в JavaScript рекурсия может привести к ошибкам stack frame errors, когда предел стека уже достигнут, а базовое условие ещё не выполнено. В таком случае, итеративный подход будет работать лучше.

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

Давайте представим, что помимо тех чисел, которые мы использовали в предыдущем примере, нам нужно учитывать и другие данные. Например, мы можем отслеживать то, как регулярные платежи влияют на срок кредита. Возможно, мы захотим остановить цикл до завершения последовательности. Если общее количество раз, когда начисляются проценты по кредиту равно 120, то и длина списка равна 120. Но, если сумма кредита будет равна 0 уже после 100 итераций, то в конце списка останется 20 неиспользуемых и ненужных элементов списка. Проблема дальнейшего усложнения сценария цикла заключается в том, что значения переменных, таких как сумма кредита, зависит от значения той же переменной на предыдущей итерации. Дело не в том, что это сложно реализовать, а в том, что это грязно.

Читайте также:  Как открыть настройки через командную строку

Визуализация данной проблемы:

Рекурсивные структуры данных

Именно в таких случаях рекурсивные структуры данных особенно полезны. Структуру можно назвать рекурсивной, если её можно определить в терминах меньшей версии самой себя. Список является примером рекурсивной структуры данных.

Например, возьмём такой список:

Теперь, сделаем на его основе два меньших списка:

Если вывести оба списка, то мы увидим следующее:

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

Пример того, как это сделать:

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

Вот как это работает на примере с вычислением сложного процента:

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

Выходные данные:

Визуализация процессов рекурсивной функции:

При каждом рекурсивном вызове мы будем брать первый элемент массива из списка. Затем мы изменим значения этого элемента и снова вызовем функцию, но на этот раз передадим ей в качестве параметров array[:1] и array[1:]. На картинке видно, что, достигнув середины списка, мы будем иметь две его части одинакового размера. А уже к концу мы полностью переберём и модифицируем все элементы первого списка, и добавим их во второй список. Далее мы шаг за шагом реализуем эту функцию в коде.

Шаг 1: создаём массив

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

Шаг 2: создаём функцию и базовое условие

Базовое условие будет учитывать два возможных сценария. Либо счётчик достигнул конца последовательности ( len(inputArr) == 0 ), либо мы погасили кредит раньше ( inputArr[-1][‘principal amount’] ).

Шаг 3: создаём выражение else и определяем переменные current, inputArray и outputArray

На данном этапе мы извлекаем текущий элемент current из массива inputArr . Ещё здесь определён массив выходных данных. Получить доступ к массиву входных данных, можно через переменную inputArr .

Шаг 4: если массив outputArray пуст, то берём первый элемент из массива входных данных и помещаем его в массив выходных данных без изменений.

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

Шаг 5: если массив выходных данных не пуст, то изменяем все значения текущего элемента.

На этом этапе мы можем вывести переменную newCurrent , которая является модифицированной версией переменной current . Она содержит в себе актуальные данные после начисления процента и платежа по кредиту. Далее нам нужно добавить эту переменную к массиву выходных данных.

Шаг 6: добавляем переменную newCurrent к массиву outputArray

Шаг 7: вызываем рекурсивную функцию с новыми параметрами

Мы закончили! Так выглядит код целиком:

Чтобы убедиться, что код работает так, как мы задумали, давайте увеличим сумму платежа.

Если изменить сумму платежа на 2000, то при выводе должны получиться такие данные:

Такой код возвращает более чистый результат, чем при использовании цикла. Если бы мы использовали итеративный подход, то нам пришлось бы перебрать все 120 элементов, большинство из которых были бы бесполезны/пусты.

Заключение

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector