Рекурсия и цикл, в чем разница? На примере Python
Цикл — это фундаментальный инструмент в программировании. Существует множество различных типов циклов, но почти все они выполнят одну базовую функцию: повторение определённых действий над данными, для их анализа или управления ими. Рекурсия, так же распространённый способ анализировать и манипулировать данными, как и цикл, но как правило, менее понятный и часто более запутанный. Почти все рекурсивные функции можно переписать в циклы, и наоборот. Тем не менее, каждый тип функции имеет свои преимущества и недостатки, и сегодня вы узнаете, в каких случаях применять тот или иной метод. В статье мы разберём следующие вопросы:
- Что такое цикл?
- Что такое рекурсия?
- Практические примеры каждого метода
- В каких случаях применять тот или иной метод
- Как выглядит рекурсивная структура данных
Начнём с метода, который кажется более простым из этих двух.
Циклы 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
Давайте разберём более сложную задачу. Нужно определить стоимость кредита или инвестиции со сложным процентом. Чтобы это сделать, нам нужны следующие данные:
- Срок кредита в годах
- Процентная ставка
- Количество платежей в год
- Сумма кредита
Формула расчёта сложного процента:
Так мы можем рассчитать всю сумму сразу. Но вместо этого, для расчёта мы используем цикл или рекурсию. В таком случае переменная времени (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’] <= 0 ).
Шаг 3: создаём выражение else и определяем переменные current, inputArray и outputArray
На данном этапе мы извлекаем текущий элемент current из массива inputArr . Ещё здесь определён массив выходных данных. Получить доступ к массиву входных данных, можно через переменную inputArr .
Шаг 4: если массив outputArray пуст, то берём первый элемент из массива входных данных и помещаем его в массив выходных данных без изменений.
Теперь оба массива выглядят как на картинке, которую вы видели выше, в момент первого вызова рекурсивной функции.
Шаг 5: если массив выходных данных не пуст, то изменяем все значения текущего элемента.
На этом этапе мы можем вывести переменную newCurrent , которая является модифицированной версией переменной current . Она содержит в себе актуальные данные после начисления процента и платежа по кредиту. Далее нам нужно добавить эту переменную к массиву выходных данных.
Шаг 6: добавляем переменную newCurrent к массиву outputArray
Шаг 7: вызываем рекурсивную функцию с новыми параметрами
Мы закончили! Так выглядит код целиком:
Чтобы убедиться, что код работает так, как мы задумали, давайте увеличим сумму платежа.
Если изменить сумму платежа на 2000, то при выводе должны получиться такие данные:
Такой код возвращает более чистый результат, чем при использовании цикла. Если бы мы использовали итеративный подход, то нам пришлось бы перебрать все 120 элементов, большинство из которых были бы бесполезны/пусты.
Заключение
На первый взгляд рекурсия может показаться сложной. Но в некоторых случаях, рекурсивный метод невероятно эффективен, если всё сделать правильно. Тем не менее, иногда лучше использовать циклы. Понимание обоих методов и умение эффективно их использовать поможет вам в работе и будет преимуществом на собеседовании.
Рекурсия и итерация
Когда мы начинаем познавать азы программирования, как правило первой написанной нами является программа, печатающая строку «Hello, world!». Потом знакомятся с переменными, операторами, функциями. И как правило, первыми, с которыми начинает знакомиться новичок, являются условный оператор и оператор цикла. Сразу же появляется желание написать какую-нибудь простую функцию: факториал числа, возведение в степень или вычисление биномиального коэффициента. При этом в большинстве случаев начинающий программист реализует итеративный вариант функций. Однако мало кто знает, что любую итеративную функцию можно реализовать и рекурсивно.
Рекурсией называется такой способ организации обработки данных, при котором программа (или функция) вызывает сама себя или непосредственно, или из других программ (функций).
Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.
Итерацией называется такой способ организации обработки данных, при котором некоторые действия многократно повторяются, не приводя при этом к рекурсивным вызовам программ (функций).
Теорема. Произвольный алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационной форме и наоборот.
Далее рассмотрим набор элементарных функций, реализованных как при помощи операторов цикла, так и при помощи рекурсивного подхода. Перед написанием рекурсивных функций на любом языке программирования, как правило, необходимо записать рекуррентное соотношение, определяющее метод вычисления функций. Рекуррентное соотношение должно содержать как минимум два условия:
I) условие продолжения рекурсии (шаг рекурсии);
II) условие окончания рекурсии.
Рекурсию будем реализовывать посредством вызова функции самой себя. При этом в теле функции сначала следует проверять условие продолжения рекурсии. Если оно истинно, то выходим из функции. Иначе совершаем рекурсивный шаг.
Итеративный вариант функций будем реализовывать при помощи оператора цикла for.
1. Факториал числа. Факториалом целого неотрицательного числа n называется произведение всех натуральных чисел от 1 до n и обозначается n!. Если f(n) = n!, то имеет место рекуррентное соотношение:
Первое равенство описывает шаг рекурсии – метод вычисления f(n) через f(n – 1). Второе равенство указывает, когда при вычислении функции следует остановиться. Если его не задать, то функция будет работать бесконечно долго.
Например, значение f(3) можно вычислить следующим образом:
Очевидно, что при вычислении f(n) следует совершить n рекурсивных вызовов.
Рекурсия и итерация
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно.
Для обоснования можно привести такие доводы.
Для начала можно вспомнить определение рекурсии и итерации. Рекурсия — это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ. Итерация — это способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.
После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий — итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно — завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.
Задача по приведению рекурсии к итеративному подходу симметрична.
Подводя итог, можно выразить такие мысли: для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче.