Автор оригинала: Marcus Sanatan.
Вступление
Когда мы думаем о повторении задачи, мы обычно думаем о циклах for и while . Эти конструкции позволяют нам выполнять итерацию над списком, коллекцией и т. Д.
Однако есть и другая форма повторения задачи, немного в другой манере. Вызывая функцию внутри себя, чтобы решить меньший экземпляр той же проблемы, мы выполняем рекурсию .
Эти функции вызывают себя до тех пор, пока проблема не будет решена, практически разделяя исходную задачу на множество меньших экземпляров самой себя – например, принимая небольшие кусочки большего куска пищи.
Конечная цель состоит в том, чтобы съесть всю тарелку горячих карманов, вы делаете это, откусывая снова и снова. Каждый укус-это рекурсивное действие, после которого вы выполняете то же самое действие в следующий раз. Вы делаете это для каждого укуса, оценивая, что вам нужно взять еще один, чтобы достичь цели, пока на вашей тарелке не останется горячих карманов.
Что такое Рекурсия?
Как указано во введении, рекурсия включает в себя процесс, вызывающий себя в определении. Рекурсивная функция обычно имеет два компонента:
- Базовый случай , который является условием, определяющим, когда рекурсивная функция должна остановиться Зов к самому себе
Давайте рассмотрим небольшой пример, чтобы продемонстрировать оба компонента:
# Assume that remaining is a positive integer
def hi_recursive(remaining):
# The base case
if remaining == 0:
return
print('hi')
# Call to function, with a reduced remaining count
hi_recursive(remaining - 1)
Базовый случай для нас – это если оставшаяся переменная равна 0 то есть сколько оставшихся строк "привет" мы должны напечатать. Функция просто возвращается.
После оператора print мы снова вызываем hi_recursive , но с уменьшенным оставшимся значением. Это очень важно! Если мы не уменьшим значение remaining , функция будет работать бесконечно. Как правило, когда рекурсивная функция вызывает саму себя, параметры изменяются, чтобы быть ближе к базовому случаю.
Давайте визуализируем, как это работает, когда мы вызываем hi_recursive(3) :
После того как функция напечатает “hi”, она вызывает себя с меньшим значением для оставшегося до тех пор, пока не достигнет 0 . При нуле функция возвращается туда, где она была вызвана в hi_recursive(1) , которая возвращается туда, где она была вызвана в hi_recursive(2) и которая в конечном счете возвращается туда, где она была вызвана в hi_recursive(3) .
Почему бы не использовать петлю?
Весь обход может быть обработан с помощью петель. Тем не менее, некоторые проблемы часто легче решаются с помощью рекурсии, а не итерации. Распространенным случаем использования рекурсии является обход дерева:
При использовании рекурсии обычно легче думать о прохождении через узлы и листья дерева. Несмотря на то, что циклы и рекурсия пересекают дерево, они имеют разные цели – циклы предназначены для повторения задачи, в то время как рекурсия предназначена для разбиения большой задачи на более мелкие задачи.
Рекурсия с деревьями, например, хорошо разветвляется, потому что мы можем обрабатывать все дерево, обрабатывая меньшие части дерева по отдельности.
Примеры
Лучший способ освоиться с рекурсией или любой другой концепцией программирования-это практиковать ее. Создание рекурсивных функций очень просто: обязательно включите свой базовый случай и вызовите функцию таким образом, чтобы она приблизилась к базовому случаю.
Сумма списка
Python включает в себя функцию sum для списков. Реализация Python по умолчанию, CPython, использует неопределенный цикл for-loop в C для создания этих функций (исходный код здесь для тех, кто заинтересован). Давайте посмотрим, как это сделать с помощью рекурсии:
def sum_recursive(nums):
if len(nums) == 0:
return 0
last_num = nums.pop()
return last_num + sum_recursive(nums)
Базовый случай – это пустой список-лучшая сумма для этого 0 . Как только мы разберемся с нашим базовым случаем, мы удалим последний элемент списка. Наконец, мы вызываем функцию sum_recursive с уменьшенным списком и добавляем число, которое мы вытащили, в общую сумму.
В интерпретаторе Python sum([10, 5, 2]) и sum_recursive([10, 5, 2]) должны ли оба дать вам 17 .
Факториальные числа
Вы можете вспомнить, что факториал положительного целого числа является произведением всех целых чисел, предшествующих ему. Следующий пример сделает это более ясным:
5! = 5 x 4 x 3 x 2 x 1 = 120
Восклицательный знак обозначает факториал, и мы видим, что умножаем 5 произведением всех целых чисел из 4 тиль 1 . Что если кто-то войдет 0 ? Широко известно и доказано, что 0! . Теперь давайте создадим функцию, как показано ниже:
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
Мы обслуживаем те случаи, когда 1 или 0 вводится, а в противном случае мы умножаем текущее число на факториал числа, уменьшенного на 1 .
Простая проверка в вашем интерпретаторе Python покажет, что factorial(5) дает вам 120 .
Последовательность Фибоначчи
A Последовательность Фибоначчи – это та, где каждое число является суммой следующих двух чисел. Эта последовательность делает предположение, что числа Фибоначчи для 0 и 1 также равны 0 и 1. Таким образом, эквивалент Фибоначчи для 2 будет равен 1.
Давайте посмотрим последовательность и соответствующие им натуральные числа:
Integers: 0, 1, 2, 3, 4, 5, 6, 7
Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13
Мы можем легко закодировать функцию в Python для определения эквивалента фибоначчи для любого положительного целого числа с помощью рекурсии:
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
Вы можете проверить, что он работает так, как ожидалось, проверив, что фибоначчи(6) равно 8 .
Теперь я хотел бы, чтобы вы рассмотрели другую реализацию этой функции, которая использует цикл for:
def fibonacci_iterative(n):
if n <= 1:
return n
a = 0
b = 1
for i in range(n):
temp = a
a = b
b = b + temp
return a
Если целое число меньше или равно 1, то верните его. Теперь, когда наш базовый случай решен. Мы постоянно добавляем первое число со вторым, сохраняя первое число в переменной temp перед его обновлением.
Выход такой же, как и у первой функции fibonacci () . Эта версия быстрее рекурсивной, так как реализации Python не оптимизированы для рекурсии, но превосходят императивное программирование. Решение, однако, не так легко читается, как наша первая попытка. Здесь кроется одна из величайших сильных сторон рекурсии: элегантность . Некоторые программные решения наиболее естественно решаются с помощью рекурсии.
Вывод
Рекурсия позволяет разбить большую задачу на более мелкие задачи, многократно вызывая саму себя. Рекурсивная функция требует, чтобы базовый случай прекратил выполнение, и вызов самой себя, который постепенно приводит функцию к базовому случаю. Он обычно используется в деревьях, но другие функции могут быть написаны с помощью рекурсии, чтобы обеспечить элегантные решения.