Вступление

Когда мы думаем о повторении задачи, мы обычно думаем о циклах 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) 

Базовый случай для нас - если remaining переменная равна 0 то есть сколько оставшихся строк «привет» мы должны напечатать. Функция просто возвращается.

После оператора печати мы hi_recursive но с уменьшенным оставшимся значением. Это важно! Если мы не уменьшим remaining значение, функция будет работать бесконечно. Обычно, когда рекурсивная функция вызывает сама себя, параметры меняются, чтобы быть ближе к базовому случаю.

Давайте визуализируем, как это работает, когда мы вызываем hi_recursive(3) :

{.ezlazyload}

После того, как функция напечатает "привет", она вызывает себя с меньшим значением, чтобы remaining пока не достигнет 0 . При нуле функция возвращается туда, где она была вызвана в hi_recursive(1) , которая возвращается туда, где она была вызвана в hi_recursive(2) и в конечном итоге возвращается туда, где она была вызвана в hi_recursive(3) .

Почему бы не использовать петлю?

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

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

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

Примеры

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

Сумма списка

Python включает функцию sum для списков. Реализация Python по умолчанию, CPython, использует неопределенный цикл for в C для создания этих функций (исходный код здесь для тех, кто заинтересован). Посмотрим, как это сделать с помощью рекурсии:

 def sum_recursive(nums): 
 if len(nums) == 0: 
 return 0 
 
 last_num = nums.pop() 
 return last_num + sum_recursive(nums) 

Базовый случай - пустой список - лучшая sum для этого - 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! = 1 . Теперь давайте создадим функцию, как показано ниже:

 def factorial(n): 
 if n == 0 or n == 1: 
 return 1 
 return n * factorial(n - 1) 

Мы учитываем случаи, когда 1 или 0 , а в противном случае мы умножаем текущее число на факториал числа, уменьшенного на 1 .

Простая проверка в интерпретаторе Python покажет, что factorial(5) дает 120 .

Последовательность Фибоначчи

Последовательность Фибоначчи - это последовательность, в которой каждое число является суммой следующих двух чисел. Эта последовательность предполагает, что числа Фибоначчи для 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) 

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

Заключение

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