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

Рекурсивная функция в 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
Если очень просто, то рекурсивными функциями считаются те функции, которые вызывают сами себя. 
Например, напишем функцию для вычисления факториала:
factorial(5) = 120 factorial(3) = 6 factorial(7) = 5040
Сначала сделаем это с помощью цикла:






def factorial(number): x = 1 for i in range(1, number+1): x *= i return x factorial(5) #returns 120
И теперь решение с помощью рекурсивной функции:
def factorial(number): if number == 1: return 1 return number * factorial(number - 1) factorial(5) #returns 120
Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы, а наоборот, может ее замедлить. Но рекурсия делает код более понятным для программиста и в такой код проще вносить изменения.
Стек вызовов
Для понимая того как работают рекурсивные функции, нужно понимать, что такое стек вызовов.






В каждой программе есть специальный стек, в котором сохраняется информация о вызовах функций. Он называется стек вызовов и именно с его помощью программа запоминает, куда она должна вернуться и ещё множество других вещей. Стеки работает по принципу LIFO (last in, first out).
Стек вызовов работает так:

При вызове вложенной функции, основная функция, откуда был вызов останавливается и создается блок памяти по новый вызов.
В ячейку памяти записываются значения переменных и адрес возврата (место, откуда была вызвана функция).
Если вызовов других функций нет, то из вложенной функции управление возвращается в основную.

Когда вы вызываете функцию из функции, вызывающая функция временно приостанавливается в частично завершенном состоянии.






Лучше всего схематично посмотреть на то, как выглядит стек. По сути это некая стопка, где программа хранит определенные данные, некий контекст вызова (значения, адрес возврата и пр.).
Более схематично разобраться с тем, как работает рекурсивная функцию можно на pythontutor.com для примера возьмите код, который был дан выше.
Рекурсивный и базовый случаи
Так как рекурсивная функция вызывает саму себя, то достаточно легко ошибиться и сделать такой вызов бесконечным ��






P.S. На самом деле бесконечным он не будет, так как рано или поздно переполниться стек. Но если что-то пошло не так нажмите в терминале Ctrl (Cmd) + C.
Итак, рекурсия всегда делится на базовый и рекурсивный случаи.
Когда вы пишите рекурсивную функцию, то обязательно нужно указать случай, когда рекурсия должна прерваться — это и есть базовый случай.






Рекурсивный случай отвечает за рекурсию и приведению к базовому случаю.
Вернемся к примеру с вычислением факториала:
def factorial(number): if number == 1: return 1 return number * factorial(number - 1)
Здесь за базовый случай отвечает кусок кода:






if number == 1: return 1
А за рекурсивный:
return number * factorial(number - 1)
В рекурсивном случае мы на каждом новом вызове функции уменьшаем значение number и тем самым, с каждым шагом, становимся всё ближе к базовому случаю. Если бы на последней строке мы указали return number * factorial(number) , то функция бы зависла, так как значение number оставалось бы неизменным.
Примеры
Напишем несколько рекурсивных функций, чтобы чуть больше разобраться с тем как это устроено: функцию для суммирования массива чисел, функцию для поиска наибольшего числа в массиве и бинарный поиск.






Функция sum_numbers
Для начала нам нужно определить базовый и рекурсивный случай. 
Базовым случаем здесь может быть пустой массив или массив из одного элемента. В случае с пустым массивом нам нужно будет вернуть 0, а с одним элементом — его значение. Я буду придерживаться того, что базовый случай это пустой массив.
def sum_numbers(numbers): if len(numbers) == 0: return 0 return numbers[0] + sum_numbers(numbers[1:])
Выше в коде происходит следующее:

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







Вот как это выглядит при визуализации на pythontutor.com 
Важно отметить, что этот пример академический и его не стоит использовать в работе, т.к. в питоне есть встроенная функция sum() .
Поиск наибольшего числа в массиве
def get_max_value(numbers): if len(numbers) == 2: if numbers[0] > numbers[1]: return numbers[0] else: return numbers[1] max_value = get_max_value(numbers[1:]) if numbers[0] > max_value: return numbers[0] else: return max_value
Тут нужно понять следующее — с помощью рекурсии мы сокращаем наш массив до базового случая, когда остается всего лишь два числа. Эти числа мы сравниваем между собой и возвращаем наибольшее число из двух. 
В max_value на «обратном проходе» сначала сохранится результат сравнения двух последних чисел массива, далее в последнем блоке if мы будем сравнивать что больше — текушее максимальное значение или первый элемент массива, который сейчас в блоке стека.






Опять же, данный пример скорее академический, потому что код с циклом будет выглядеть гораздо проще и читабельнее:
def get_max_value(numbers): max_value = 0 for number in numbers: if number > max_value: max_value = number return max_value
Бинарный поиск
def bin_search(target, numbers, left_position, right_position): if right_position target: return bin_search(target, numbers, left_position, mid_position) else: return bin_search(target, numbers, mid_position + 1, right_position)
На вход нам нужно получить помимо целевого числа для поиска и отсортированного массива нужно получить левую позицию и правую (начало и конец массива). Внутри функции их определить не выйдет, так как они будут на каждом проходе рекурсии меняться.
Далее по алгоритму:







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

На каждом проходе значение mid_position сдвигается правее или левее, но сам массив остается неизменным.
Python для подготовки к олимпиадам, начальный уровень (7-9 классы) (СОШ г. Набережные Челны)
Ранее была задача вычисления числа сочетаний из n элементов по k, для чего необходимо вычисление факториалов трех величин: n, k и n-k. Для этого можно сделать три цикла, что приводит к увеличению размера программы за счет трехкратного повторения похожего кода. Вместо этого лучше сделать одну функцию, вычисляющую факториал любого данного числа n и трижды использовать эту функцию в своей программе. Соответствующая функция может выглядеть так:
def factorial(n): f = 1 for i in range(2, n + 1): f *= i return f 
Этот текст должен идти в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial. Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.
Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной f. Функция завершается инструкцией return f, которая завершает работу функции и возвращает значение переменной f. Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения, также в функциях, не возвращающих значения, инструкция return может отсутствовать.
Теперь мы можем использовать нашу функцию несколько раз. В этом примере мы трижды вызываем функцию factorial для вычисления трех факториалов: factorial(n), factorial(k), factorial(n-k) .
n = int(input()) k = int(input()) print(factorial(n) // (factorial(k) * factorial(n - k))) 
Мы также можем, например, объявить функцию binomial, которая принимает два целочисленных параметра n и k и вычисляет число сочетаний из n по k:
def binomial(n, k) return factorial(n) // (factorial(k) * factorial(n - k)) 
Тогда в нашей основной программе мы можем вызвать функцию binomial для нахождения числа сочетаний:
print binomial(n, k) 
Вернемся к задаче нахождения наибольшего из двух или трех чисел. Функцию нахождения максимума из двух чисел можно написать так:
def max(a, b): if a > b: return a else: return b 
Теперь мы можем реализовать функцию max3, находящую максимум трех чисел:
def max3(a, b, c): return max(max(a, b), c) 
Функция max3 дважды вызывает функцию max для двух чисел: сначала, чтобы найти максимум из a и b, потом чтобы найти максимум из этой величины и c.
Что такое рекурсивная функция в Python?
Рекурсивная функция - это функция, содержащая в теле вызов самой себя. Помимо такого вызова, в теле функции обязательно должно быть терминальное условие, которое остановит повторные вызовы, чтобы они не стали бесконечными.
def factorial(n): # терминальное условие, которое остановит рекурсию if n  0: return 1 # рекурсивный вызов return n * factorial(n - 1) factorial(5) # 120 # тоже самое, что 5 * 4 * 3 * 2 * 1 
Дополнительно можно посмотреть вот это короткое видео , тут очень понятно объясняется понятие рекурсии (с 2:45 примерно)


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

Как обновить pip в pycharm
Как посмотреть когда был выключен компьютер
Как разобрать мотор пылесоса самсунг
Как удалить приложение с айфона полностью из облака