Цикл — это фундаментальный инструмент в программировании. Существует множество различных типов циклов, но почти все они выполнят одну базовую функцию: повторение определённых действий над данными, для их анализа или управления ими. Рекурсия, так же распространённый способ анализировать и манипулировать данными, как и цикл, но как правило, менее понятный и часто более запутанный. Почти все рекурсивные функции можно переписать в циклы, и наоборот. Тем не менее, каждый тип функции имеет свои преимущества и недостатки, и сегодня вы узнаете, в каких случаях применять тот или иной метод. В статье мы разберём следующие вопросы:
- Что такое цикл?
- Что такое рекурсия?
- Практические примеры каждого метода
- В каких случаях применять тот или иной метод
- Как выглядит рекурсивная структура данных
Начнём с метода, который кажется более простым из этих двух.
Циклы for
Цикл for используют для перебора последовательности данных (списка, кортежа, словаря, набора или строки). При достижении конца последовательности цикл завершается.
Например, вам нужно сложить числа от 1 до 5 и получить их сумму. Конечно, вы можете просто суммировать 1+2+3+4+5. Но, создать функцию намного удобнее, потому что вы сможете использовать её повторно, причём подставляя любые значения, даже если они не известны заранее.
Это будет выглядеть примерно так:
Для работы такого цикла, нам нужно хранить список всех чисел, чтобы мы могли перебирать элементы и складывать их в итоговое значение.
Вот как это выглядит в коде:
def getTotal(n):
total = 0
for number in list(range(n+1)):
print number
total = total + number
return total
print getTotal(5)В начале, функция принимает число в качестве параметра. Возьмём число 5 для примера. Далее мы создаём переменную для хранения результата и устанавливаем её значение на 0. После этого начинаем перебирать список чисел от 0 до n+1 . Мы должны указать именно n+1 , потому что иначе выражение list(range(n)) не будет включать n , т.е. будет суммировать 0,1,2,3,4.
Запустив код, мы увидим, что все числа на своих местах и нам возвращается их сумма.
Вывод функции:
0
1
2
3
4
5
15
Рекурсия
Если функция вызывает сама себя, то это является признаком рекурсии. Одно из важнейших отличий рекурсии от цикла, это способ завершения рекурсивной функции. В приведённом выше примере цикл for завершается в конце последовательности, в которой он выполняется. А вот рекурсивная функция может продолжаться бесконечно, потому что она может не иметь последовательности данных. Вместо этого у рекурсивной функции есть так называемое базовое условие. Базовое условие определяет, когда цикл должен завершится.
Давайте попробуем решить предыдущую задачу рекурсивным способом. Визуально это выглядит так:
Каждый раз функция либо вызывает себя с новыми входными данными, либо возвращает значение.
Вот как это выглядит в коде:
def getTotal(n, total):
print n
if n == 0: # base condition
return total
else:
return getTotal(n-1, (total+(n)))
print getTotal(5, 0)Как видите мы передаём два значения: начальное и итоговое. При первом вызове функции итоговое значение равно 0, а начальное 5. Мы проверяем, является ли начальное число 0. Если нет, то вызываем функцию снова, но на этот раз мы меняем входное значение на 5–1 и 0+5, и повторяем этот процесс до тех пор, пока n не будет равно 0. После выполнения этого условия мы возвращаем итоговое значение (15).
Вычисление сложного процента рекурсией и циклом FOR
Давайте разберём более сложную задачу. Нужно определить стоимость кредита или инвестиции со сложным процентом. Чтобы это сделать, нам нужны следующие данные:
- Срок кредита в годах
- Процентная ставка
- Количество платежей в год
- Сумма кредита
Формула расчёта сложного процента:
Так мы можем рассчитать всю сумму сразу. Но вместо этого, для расчёта мы используем цикл или рекурсию. В таком случае переменная времени (nt) будет обрабатываться в итерациях.
Давайте сразу создадим переменные, в которых будем хранить исходные числа и используем их в обоих методах:
durationInYears = 10
interestRate = .06
compoundedPerYear = 12
principalAmount = 4000
Расчёт по сложной процентной ставке итеративно
Давайте сразу посчитаем общее количество платежей, чтобы упростить вычисление в цикле. Так как платежи ежемесячные, а количество лет равно 10, то результат будет 120, или 10*12. Теперь мы можем вычислять процент для каждого месяца и добавлять результат каждой итерации к основной сумме.
Так выглядит код:
def compoundInterest(principal, compounded, duration, rate):
totalCompounded = duration * compounded
for i in range(1, (totalCompounded+1)):
principal = principal*(1+(rate/compounded))
return principal
print (compoundInterest(principalAmount, compoundedPerYear, durationInYears, interestRate))Единственное различие между этим и предыдущим примерами заключается в том, что мы делаем на несколько вычислений больше во время каждой итерации. Также увеличилось число итераций с 5 до 120.
Результат наших вычислений:
7277.58693613
Расчёт по сложной процентной ставке рекурсивным способом
В предыдущем примере последовательность данных равна 120, что отражает количество раз, когда основная сумма пересчитывается. Цикл прерывается по завершении последовательности. Рекурсивный метод позволяет нам поступить схожим образом, т.е. инициализировать счётчик и задать два условия.
- Условие 1: Счётчик не равен 0.
Выполнить вычисление сложного процента. Добавить результат вычисления к общей сумме. Уменьшить значение счётчика на 1. Повторить те же действия, подставив новое значения для счётчика и общей суммы.
- Условие 2: Счётчик равен 0
Возврат общей суммы
В предыдущем примере, цикл функции начинался со значения 5 и завершался при 0.
Здесь происходит тоже самое, только начальное значение теперь 120
def compoundRecursion(principal, compounded, duration, rate, numberOfRecursions):
if numberOfRecursions == 0:
totalDuration = compounded * duration
elif numberOfRecursions != 0:
totalDuration = duration
if duration == 0:
return principal
else:
newDuration = totalDuration - 1
amount = principal*(1+(rate/compounded))
return compoundRecursion(amount, compounded, newDuration, rate, 1)
print (compoundRecursion(principalAmount, compoundedPerYear, durationInYears, interestRate, 0))Здесь мы либо снова вызываем функцию, либо возвращаем обновлённую общую сумму. Каждый раз вызывая функцию, значение счётчика уменьшается на 1. Возврат общей суммы происходит, когда счётчик равен 0.
Когда использовать рекурсию
Выбор между рекурсивным и итеративным методом может в значительной степени зависеть от языка, который вы используете, или от задачи, которую вы намерены решить. Например, в JavaScript рекурсия может привести к ошибкам stack frame errors, когда предел стека уже достигнут, а базовое условие ещё не выполнено. В таком случае, итеративный подход будет работать лучше.
Рассмотренный выше случай является хорошим примером того, когда рекурсия работает намного лучше, чем цикл.
Давайте представим, что помимо тех чисел, которые мы использовали в предыдущем примере, нам нужно учитывать и другие данные. Например, мы можем отслеживать то, как регулярные платежи влияют на срок кредита. Возможно, мы захотим остановить цикл до завершения последовательности. Если общее количество раз, когда начисляются проценты по кредиту равно 120, то и длина списка равна 120. Но, если сумма кредита будет равна 0 уже после 100 итераций, то в конце списка останется 20 неиспользуемых и ненужных элементов списка. Проблема дальнейшего усложнения сценария цикла заключается в том, что значения переменных, таких как сумма кредита, зависит от значения той же переменной на предыдущей итерации. Дело не в том, что это сложно реализовать, а в том, что это грязно.
Визуализация данной проблемы:
Рекурсивные структуры данных
Именно в таких случаях рекурсивные структуры данных особенно полезны. Структуру можно назвать рекурсивной, если её можно определить в терминах меньшей версии самой себя. Список является примером рекурсивной структуры данных.
Например, возьмём такой список:
Теперь, сделаем на его основе два меньших списка:
Если вывести оба списка, то мы увидим следующее:
Благодаря рекурсивным функциям и рекурсивными структурам данных мы можем изменить весь список или меньшую часть большего списка за раз. Итеративный подход решения подобной проблемы, позволяет изменить только одно значение в одном индексе за раз.
Пример того, как это сделать:
Сохранив маленькие части большого списка, мы можем вызвать ту же функцию (рекурсия) и отправить ей эти части (рекурсивная структура данных).
Вот как это работает на примере с вычислением сложного процента:
def recursiveData(data):
# Base Condition ( if principal amount == 0 or if duration == 0)
# Else Condition ( recalculate the times compounded, duration & principal amount)
print (recursiveData(array))Наша функция в основном состоит из операторов if и else. Мы можем усложнить эту структуру если понадобится, но она и в таком виде делает всё что нам нужно. В итоге, мы хотим вернуть окончательные данные, которые покажут нам сумму кредита и размер текущего платежа на каждой итерации, когда начисляется процент.
Выходные данные:
[
{
'times compounded': 0,
'duration remaining': 10,
'interest rate': .06,
'current payment': 100,
'compounded per year': 12,
'principal amount': 4000
},
{
'times compounded': 1,
'duration remaining': 10,
'interest rate': .06,
'current payment': 100,
'compounded per year': 12,
'principal amount': 3900
}
]Визуализация процессов рекурсивной функции:
При каждом рекурсивном вызове мы будем брать первый элемент массива из списка. Затем мы изменим значения этого элемента и снова вызовем функцию, но на этот раз передадим ей в качестве параметров array[:1] и array[1:]. На картинке видно, что, достигнув середины списка, мы будем иметь две его части одинакового размера. А уже к концу мы полностью переберём и модифицируем все элементы первого списка, и добавим их во второй список. Далее мы шаг за шагом реализуем эту функцию в коде.
Шаг 1: создаём массив
durationInYears = 10
compoundedPerYear = 12
array = [{
'times compounded': 0,
'duration remaining': 10,
'interest rate': .06,
'current payment': 50,
'compounded per year': 12,
'principal amount': 4000,
'total compounded': compoundedPerYear*durationInYears
}]*(compoundedPerYear*durationInYears)На данном этапе, наш массив имеет длину равную числу раз, когда начисляется процент. Каждый элемент содержит одинаковые данные, которые мы будем изменять рекурсивно.
Шаг 2: создаём функцию и базовое условие
def recursiveData(inputArr, outputArr):
if len(inputArr) == 0 or inputArr[-1]['principal amount'] <= 0:
return outputArr
Базовое условие будет учитывать два возможных сценария. Либо счётчик достигнул конца последовательности (len(inputArr) == 0), либо мы погасили кредит раньше ( inputArr[-1][‘principal amount’] <= 0).
Шаг 3: создаём выражение else и определяем переменные current, inputArray и outputArray
else:
current = inputArr[:1][0]
inputArrayLength = len(inputArr[1:])
outputArray = outputArr
На данном этапе мы извлекаем текущий элемент current из массива inputArr. Ещё здесь определён массив выходных данных. Получить доступ к массиву входных данных, можно через переменную inputArr.
Шаг 4: если массив outputArray пуст, то берём первый элемент из массива входных данных и помещаем его в массив выходных данных без изменений.
if len(outputArray) == 0:
outputArray.append(current)
return recursiveData(inputArr[1:], outputArray)
Теперь оба массива выглядят как на картинке, которую вы видели выше, в момент первого вызова рекурсивной функции.
Шаг 5: если массив выходных данных не пуст, то изменяем все значения текущего элемента.
else:
newTimesCompounded = outputArray[-1]['times compounded'] + 1
newDurationRemaining = current['duration remaining']
if ((outputArray[-1]['times compounded'] + 1) % 12) == 0:
newDurationRemaining = outputArray[-1]['duration remaining'] - 1
principal = (outputArray[-1]['principal amount'])*(1+(outputArray[-1]
['interest rate']/outputArray[-1]['compounded per year']))
currentPayment = current['current payment']
if currentPayment > principal:
currentPayment = principal
newPrincipalAmount = (principal - currentPayment)
newTotalCompounded = outputArray[-1]['total compounded'] - 1
newCurrent = {
'times compounded': newTimesCompounded,
'duration remaining': newDurationRemaining,
'interest rate': current['interest rate'],
'current payment': currentPayment,
'compounded per year': current['compounded per year'],
'principal amount': newPrincipalAmount,
'total compounded': newTotalCompounded
}На этом этапе мы можем вывести переменную newCurrent, которая является модифицированной версией переменной current. Она содержит в себе актуальные данные после начисления процента и платежа по кредиту. Далее нам нужно добавить эту переменную к массиву выходных данных.
Шаг 6: добавляем переменную newCurrent к массиву outputArray
outputArray.append(newCurrent)
Шаг 7: вызываем рекурсивную функцию с новыми параметрами
return recursiveData(inputArr, outputArray)
Мы закончили! Так выглядит код целиком:
durationInYears = 10
compoundedPerYear = 12
array = [{
'times compounded': 0,
'duration remaining': 10,
'interest rate': .06,
'current payment': 2000,
'compounded per year': 12,
'principal amount': 4000,
'total compounded': compoundedPerYear*durationInYears
}]*(compoundedPerYear*durationInYears)
def recursiveData(inputArr, outputArr):
if len(inputArr) == 0 or inputArr[-1]['principal amount'] <= 0:
return outputArr
else:
current = inputArr[:1][0]
inputArrayLength = len(inputArr[1:])
outputArray = outputArr
if len(outputArray) == 0:
outputArray.append(current)
return recursiveData(inputArr[1:], outputArray)
else:
newTimesCompounded = outputArray[-1]['times compounded'] + 1
newDurationRemaining = current['duration remaining']
if ((outputArray[-1]['times compounded'] + 1) % 12) == 0:
newDurationRemaining = outputArray[-1]['duration remaining'] - 1
principal = (outputArray[-1]['principal amount'])*(1+(outputArray[-1]
['interest rate']/outputArray[-1]['compounded per year']))
currentPayment = current['current payment']
if currentPayment > principal:
currentPayment = principal
newPrincipalAmount = (principal - currentPayment)
newTotalCompounded = outputArray[-1]['total compounded'] - 1
newCurrent = {
'times compounded': newTimesCompounded,
'duration remaining': newDurationRemaining,
'interest rate': current['interest rate'],
'current payment': currentPayment,
'compounded per year': current['compounded per year'],
'principal amount': newPrincipalAmount,
'total compounded': newTotalCompounded
}
outputArray.append(newCurrent)
inputArr = [newCurrent]*inputArrayLength
return recursiveData(inputArr, outputArray)
returnData = recursiveData(array, [])
for i in returnData:
print (i)Чтобы убедиться, что код работает так, как мы задумали, давайте увеличим сумму платежа.
Если изменить сумму платежа на 2000, то при выводе должны получиться такие данные:
{'times compounded': 0, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 2000, 'compounded per year': 12, 'principal amount': 4000, 'total compounded': 120}
{'times compounded': 1, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 2000, 'compounded per year': 12, 'principal amount': 2019.9999999999995, 'total compounded': 119}
{'times compounded': 2, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 2000, 'compounded per year': 12, 'principal amount': 30.099999999999227, 'total compounded': 118}
{'times compounded': 3, 'duration remaining': 10, 'interest rate': 0.06, 'current payment': 30.25049999999922, 'compounded per year': 12, 'principal amount': 0.0, 'total compounded': 117}Такой код возвращает более чистый результат, чем при использовании цикла. Если бы мы использовали итеративный подход, то нам пришлось бы перебрать все 120 элементов, большинство из которых были бы бесполезны/пусты.
Заключение
На первый взгляд рекурсия может показаться сложной. Но в некоторых случаях, рекурсивный метод невероятно эффективен, если всё сделать правильно. Тем не менее, иногда лучше использовать циклы. Понимание обоих методов и умение эффективно их использовать поможет вам в работе и будет преимуществом на собеседовании.
Перевод статьи Ethan Jarrell: Recursion vs. Looping in Python
