Что такое рекурсия в питоне

Что такое рекурсивная функция в Python?

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

def factorial(n): # терминальное условие, которое остановит рекурсию if n  0: return 1 # рекурсивный вызов return n * factorial(n - 1) factorial(5) # 120 # тоже самое, что 5 * 4 * 3 * 2 * 1 

Дополнительно можно посмотреть вот это короткое видео , тут очень понятно объясняется понятие рекурсии (с 2:45 примерно)

Рекурсивная функция в python

Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:

• Рекурсивную функцию поиска факториала.
• Как рекурсивные функции работают в коде.
• Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?

Рекурсивные функции

Рекурсивная функция — это та, которая вызывает сама себя.

В качестве простейшего примера рассмотрите следующий код:

 
def factorial_recursive(n): 
if n == 1: 
return n 
else: 
return n*factorial_recursive(n-1) 

Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).
Вкратце о факториалах
Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.

Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040

Вывести факториал числа можно с помощью функции:
 
num = 3 
print(f"Факториал это ") 

Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:
def factorial_recursive(n): . 
По аналогии с обычной функцией имя рекурсивной указывается после def , а в скобках обозначается параметр n :






def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.
def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1 .
Это и есть рекурсия. В нашем примере это так сработало:
3 * (3-1) * ((3-1)-1) # так как 3-1-1 равно 1, рекурсия остановилась
Детали работы рекурсивной функции
Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.






Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:
 
# Первый вызов 
factorial_recursive(3): 
if 3 == 1: 
return 3 
else: 
return 3*factorial_recursive(3-1) 
 
# Второй вызов 
factorial_recursive(2): 
if 2 == 1: 
return 2 
else: 
return 2*factorial_recursive(2-1) 
 
# Третий вызов 
factorial_recursive(1): 
if 1 == 1: 
return 1 
else: 
return 1*factorial_recursive(1-1) 

Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1) , поэтому она добавляет в стек еще один вызов.
Как работает рекурсия
/\ factorial_recursive(1) - последний вызов || factorial_recursive(2) - второй вызов || factorial_recursive(3) - первый вызов
Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.
Но как только в стек добавляется вызов factorial_recursive(1) , для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.

factorial_recursive(1) завершается, отправляет 1 в
factorial_recursive(2) и выпадает из стека.
factorial_recursive(2) завершается, отправляет 2*1 в
factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.

Рекурсия в Python имеет ограничение в 3000 слоев.






 
>>> import sys 
>>> sys.getrecursionlimit() 
3000 

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

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

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






 
def factorial_iterative(num): 
factorial = 1 
if num < 0:
print("Факториал не вычисляется для отрицательных чисел") 
else: 
for i in range (1, num + 1): 
factorial = factorial*i 
print(f"Факториал это ") 

Как работает рекурсия функции: объясняем на примере Python
Чтобы понять рекурсивные алгоритмы, нужно понять рекурсивные алгоритмы. Или прочитать эту статью.
 
 
Фото: Bernard Van Berg / Getty Images






Иван Стуков

Журналист, изучает Python. Любит разбираться в мелочах, общаться с людьми и понимать их.
Мы уже рассказывали о рекурсии простыми словами и о том, где её можно встретить в реальной жизни. Пришло время объяснить, как и зачем в программировании применяют рекурсивные функции.
Что такое рекурсия: быстрое напоминание
В давние времена некоторые девушки, далёкие от точных наук, любили погадать, закрываясь ровно в полночь в чёрной-чёрной комнате и ставя свечку между двумя зеркалами. Согласно их поверьям, это открывало портал в потусторонний мир. А математики увидели бы в этом наглядное представление рекурсии.
В каждом зеркале отражалась свеча, и отражение этой свечи в другом зеркале, и отражение отражения, и отражение отражения отражения… и так до тех пор, пока девушке не померещится суженый.






Предупреждение: не пытайтесь повторить эксперимент! В кадре задействованы только профессиональные каскадёры! Ни одно животное в процессе съёмки не пострадало!

Выражаясь научным языком, рекурсия — это определение или изображение объекта или процесса внутри самого этого объекта или процесса.
Что такое рекурсия функции
Из вышеприведённого определения становится понятно, что рекурсивная функция — это такая функция, которая в процессе выполнения вызывает саму себя. Это свойство бывает полезно при выполнении некоторых задач в программировании.
Например, мы хотим написать функцию summa(n), которая считает сумму чисел от 1 до n. Если n = 2, то результат будет 1 + 2 = 3. Если n = 5, то получится 1 + 2 + 3 + 4 + 5 = 15. Реализовать такой алгоритм можно двумя способами: итерационным и рекурсивным.






Итерационный, или пошаговый, способ. Напишем цикл от 1 до n, в котором на каждом следующем шаге будем прибавлять к x номер шага. На языке Python это выглядит так:

Из команд summa(n) и возвращает x можно составить лестницу. Это буквально шаги работы рекурсивного алгоритма. Сначала он постепенно уходит вглубь рекурсии — а потом идёт в обратную сторону, возвращаясь к первоначальной функции.
На самом деле в большинстве случаев рекурсивную функцию можно заменить циклами: зачастую они работают быстрее и потребляют меньше памяти.






Но при более сложных задачах лучше написать рекурсивное решение: так оперативнее, проще и понятнее, а ещё его легче поддерживать. Нередко это становится более важным и ценным, чем эффективность выполнения кода.
Условия рекурсивных алгоритмов
Вернёмся к нашему примеру с summa(n). Чтобы алгоритм работал, программа должна соответствовать двум требованиям.
Базовый случай
Помимо рекурсивного случая, когда функция вызывает сама себя ещё раз, должно быть определённое стоп-условие, чтобы этот процесс не продолжался бесконечно и функция могла завершить работу самостоятельно. В программировании это называется базовым случаем.
У нас он произойдёт, когда n станет равным 1. Мы упростили задачу настолько, что больше нет смысла считать, — и можем просто дать ответ.
Чтобы добраться до базового случая, рекурсивной функции приходится вызывать себя определённое количество раз. Такое число самовызовов плюс первоначальный вызов функции называется глубиной рекурсии. В случае summa(5) она равна 5.






Рекурсия
Чтобы прийти к базовому случаю, мы должны передавать каждой новой функции изменённые данные. Другими словами, нужно изменять аргумент функции.
В нашем коде при первом вызове n была равна 5, при втором — 4. И так до тех пор, пока n не стала равна 1. Не сделай мы этого, рекурсия никогда бы не завершилась и бесконечно порождала бы новые функции.
Как работают рекурсивные алгоритмы
В момент, когда функция вызывает сама себя, действие «материнской» функции приостанавливается — и начинается выполнение «дочерней».
Но так как рано или поздно программа должна вернуться к «материнской» функции, нужно сохранить данные о её работе. Для этого существует стек вызовов.






Разберём это на примере вызова summa(5). Представим, что компьютер хранит данные о функции в виде блока. В нём содержится значение переменной n и кусок кода, который сейчас выполняется. Пусть он выглядит так:

В момент, когда summa(5) вызывает summa(4), создаётся новый блок и кладётся поверх предыдущего:






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

summa(1) возвращает единицу, завершает работу и покидает стек. Теперь наверху находится summa(2):

summa(2) продолжает свою работу с момента, на котором остановилась. Она заканчивает выполнять свою программу и тоже покидает стек. Теперь наверху summa(3). И так происходит с каждой функцией, пока стек не закончится.






При прочих равных программы с рекурсивными функциями обычно потребляют больше памяти, чем итерационные. Так происходит потому, что они хранят внутри стека данные обо всех незавершённых функциях.
Память и мощность любой техники ограничены, поэтому у стека всегда есть максимально допустимый размер. Например, в Python он равен 1000 вызовов. Если максимум достигнут, а мы пытаемся положить в стек ещё одну функцию, происходит ошибка «Переполнение стека».
Кстати, именно в честь этой ошибки назван популярный сайт для вопросов и ответов о программировании Stack Overflow.
Итоги
Рекурсивная функция — это функция, которая вызывает сама себя.






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

Процедуры и функции С++: как работает рекурсия в С++
«Из рекламного агентства меня уволили за то, что я учился делать сайты прямо на работе»
Как научиться программировать на любом языке

Что такое рекурсия в питоне






 
Итерацию можно назвать противоположностью рекурсии. Всегда, когда задачу можно решить итерацией (либо итерацией с использованием стека), следует делать выбор в пользу цикла for или while вместо рекурсии.
Мемоизация
Если применение рекурсии при решении задачи неизбежно, есть простой способ ускорить выполнение функции – для этого используют декоратор @lru_cache() модуля functools. Сравним скорость выполнения рекурсивного кода при решении следующей олимпиадной задачи.
Задача: лесенка представляет собой набор кубиков. В этом наборе каждый последующий ряд состоит из меньшего числа кубиков, чем предыдущий. Надо написать программу для вычисления количества лесенок, которое можно построить из n кубиков.






 
В решении используется рекурсивная функция, выполнение которой в интерпретаторе Python занимает столько времени, что готовое решение никогда не будет соответствовать строгим олимпиадным критериям. Для кэширования промежуточных результатов можно написать функцию мемоизации самостоятельно, а можно воспользоваться готовым, уже упомянутым выше декоратором. Сравним скорость выполнения решений с мемоизацией и без:
 
Пример ввода:
 
Посещаем узел Анна. Проверяем, состоит ли имя Анна из 9 букв. Посещаем узел Егор. Проверяем, состоит ли имя Егор из 9 букв. Посещаем узел Мария. Проверяем, состоит ли имя Мария из 9 букв. Посещаем узел Светлана. Проверяем, состоит ли имя Светлана из 9 букв. Посещаем узел Инга. Проверяем, состоит ли имя Инга из 9 букв. Посещаем узел Елизавета. Проверяем, состоит ли имя Елизавета из 9 букв. Имя из 9 букв: Елизавета 
root = ]>, , ]>, ]>]> def find_name(node): print(f"Посещаем узел . ") print(f"Проверяем, состоит ли имя из 9 букв. ") if len(node['name']) == 9: return node['name'] # граничный случай if len(node['children']) > 0: # рекурсивный случай for child in node['children']: returnValue = find_name(child) if returnValue != 'не найдено': return returnValue return 'не найдено' # граничный случай - имен из 9 букв нет print(f"Имя из 9 букв: ") 
Примечание: без рекурсии такую задачу можно решить с помощью ООП:
class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right def traverse(root): if root is None: return traverse(root.left) if len(root.data) == 9: print(f'Имя найдено: ') return traverse(root.right) if len(root.data) == 9: print(f'Имя найдено: ') return if __name__ == '__main__': root = Node('Анна') root.left = Node('Егор') root.right = Node('Светлана') root.left.left = Node('Мария') root.right.left = Node('Инга') root.right.right = Node('Марина') root.right.left.left = Node('Елизавета') root.right.left.right = Node('Антон') traverse(root) 
Задание 9
Имеется многомерный вложенный список:
sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] 
Напишите рекурсивную и итеративную функции для преобразования списка в одномерный.
Ожидаемый результат:
[5, 7, 2, 4, 9, 5, 2, 5, 4, 3, 2, 1, 5, 9, 5, 4, 3, 1, 2, 4, 7, 2, 6, 4, 4, 1, 6, 3, 8, 4, 5, 9, 1, 3, 1, 5, 6, 4, 2, 1, 2, 5, 6, 8, 2, 3, 4, 5, 3, 2, 2, 1, 4, 2, 5, 4, 3, 1, 6, 7, 9, 0, 5, 2, 4, 7, 3, 4, 4, 2, 5, 6, 7, 5, 7, 1, 3, 4, 6, 6, 4, 5] 
Решение 1 – рекурсивное:
def flat_list_recur(lst): if lst == []: return lst if isinstance(lst[0], list): return flat_list_recur(lst[0]) + flat_list_recur(lst[1:]) return lst[:1] + flat_list_recur(lst[1:]) sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] print(flat_list_recur(sp)) 
Решение 2 – итеративное:
def flat_list_iter(lst): result = [] stack = [lst] while stack: current = stack.pop(-1) if isinstance(current, list): stack.extend(current) else: result.append(current) result.reverse() return result sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] print(flat_list_iter(sp)) 
Задание 10
Реализуйте алгоритм бинарного поиска с помощью итеративной и рекурсивной функций. Число задается с помощью randrange(2000), в списке хранятся числа от 1 до 1000, т.е. не во всех случаях заданное число будет присутствовать в списке.
Пример вывода:
Число найдено: 787 
Решение 1 – рекурсивное:
from random import randrange def binary_recursive(lst, start, end, num): if end >= start: mid = (end + start) // 2 if lst[mid] == num: # граничный случай - элемент находится посередине return mid elif lst[mid] > num: # рекурсивный случай - элемент находится слева return binary_recursive(lst, start, mid - 1, num) else: # рекурсивный случай - элемент находится справа return binary_recursive(lst, mid + 1, end, num) else: # граничный случай - элемент в списке не обнаружен return 'не найдено' sp = [i for i in range(1001)] n = randrange(2000) result = binary_recursive(sp, 0, len(sp)-1, n) if result != 'не найдено': print(f'Число найдено: ') else: print('Такого числа нет в списке') 
Решение 2 – итеративное:
from random import randrange def binary_iter(lst, num): start, end, mid = 0, len(lst) - 1, 0 while start num: end = mid - 1 else: return mid return 'не найдено' sp = [i for i in range(1001)] n = randrange(2000) result = binary_iter(sp, n) if result != 'не найдено': print(f'Число найдено: ') else: print('Такого числа нет в списке') 
Подведем итоги
Рекурсию стоит применять для решения задач, в которых:

Используется древовидная структура данных.
Нужно предусмотреть возврат к предыдущей отправной точке (например, при поиске выхода из лабиринта).
Глубина рекурсивных вызовов находится в пределах разумного и не приведет к переполнению стека.

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

Особенности, сферы применения, установка, онлайн IDE
Все, что нужно для изучения Python с нуля – книги, сайты, каналы и курсы
Типы данных: преобразование и базовые операции
Методы работы со строками
Методы работы со списками и списковыми включениями
Методы работы со словарями и генераторами словарей
Методы работы с кортежами
Методы работы со множествами
Особенности цикла for
Условный цикл while
Функции с позиционными и именованными аргументами
Анонимные функции
Рекурсивные функции
Функции высшего порядка, замыкания и декораторы
Методы работы с файлами и файловой системой
Регулярные выражения
Основы скрапинга и парсинга
Основы ООП: инкапсуляция и наследование
Основы ООП – абстракция и полиморфизм
Графический интерфейс на Tkinter
Основы разработки игр на Pygame
Основы работы с SQLite
Основы веб-разработки на Flask
Основы работы с NumPy
Основы анализа данных с Pandas



Похожие публикации:

Как включить доступ к хранилищу на телефоне самсунг
Как удалить шаблон
Начните с яндекс браузера как заблокировать edge
Что делает операция в си шарп