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

Что такое рекурсивная функция в 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
Напомним, что в математике факториал числа n определяется как Например, Ясно, что факториал можно легко посчитать, воспользовавшись циклом for. Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода). Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.
# вычислим 3! res = 1 for i in range(1, 4): res *= i print(res) # вычислим 5! res = 1 for i in range(1, 6): res *= i print(res)
Однако, если мы ошибёмся один раз в начальном коде, то потом эта ошибка попадёт в код во все места, куда мы скопировали вычисление факториала. Да и вообще, код занимает больше места, чем мог бы. Чтобы избежать повторного написания одной и той же логики, в языках программирования существуют функции.
Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются. Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.






Покажем, как написать функцию factorial(), которая принимает один параметр — число, и возвращает значение — факториал этого числа.
def factorial(n): res = 1 for i in range(1, n + 1): res *= i return res print(factorial(3)) print(factorial(5))
Дадим несколько объяснений. Во-первых, код функции должен размещаться в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial(). Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.
Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.
Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения. В функциях, которым не нужно возвращать значения, инструкция return может отсутствовать.






Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).
10 20
def max(a, b): if a > b: return a else: return b print(max(3, 5)) print(max(5, 3)) print(max(int(input()), int(input())))
Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.
def max(a, b): if a > b: return a else: return b def max3(a, b, c): return max(max(a, b), c) print(max3(3, 5, 4))
Встроенная функция max() в Питоне может принимать переменное число аргументов и возвращать максимум из них. Приведём пример того, как такая функция может быть написана.
def max(*a): res = a[0] for val in a[1:]: if val > res: res = val return res print(max(3, 5, 4))
Все переданные в эту функцию параметры соберутся в один кортеж с именем a, на что указывает звёздочка в строке объявления функции.






2. Локальные и глобальные переменные

Внутри функции можно использовать переменные, объявленные вне этой функции
def f(): print(a) a = 1 f()
Здесь переменной a присваивается значение 1, и функция f() печатает это значение, несмотря на то, что до объявления функции f эта переменная не инициализируется. В момент вызова функции f() переменной a уже присвоено значение, поэтому функция f() может вывести его на экран.
Такие переменные (объявленные вне функции, но доступные внутри функции) называются глобальными.
Но если инициализировать какую-то переменную внутри функции, использовать эту переменную вне функции не удастся. Например:






def f(): a = 1 f() print(a)
Получим ошибку NameError: name 'a' is not defined . Такие переменные, объявленные внутри функции, называются локальными. Эти переменные становятся недоступными после выхода из функции.
Интересным получится результат, если попробовать изменить значение глобальной переменной внутри функции:
def f(): a = 1 print(a) a = 0 f() print(a)
Будут выведены числа 1 и 0. Несмотря на то, что значение переменной a изменилось внутри функции, вне функции оно осталось прежним! Это сделано в целях “защиты” глобальных переменных от случайного изменения из функции. Например, если функция будет вызвана из цикла по переменной i , а в этой функции будет использована переменная i также для организации цикла, то эти переменные должны быть различными. Если вы не поняли последнее предложение, то посмотрите на следующий код и подумайте, как бы он работал, если бы внутри функции изменялась переменная i.
def factorial(n): res = 1 for i in range(1, n + 1): res *= i return res for i in range(1, 6): print(i, '! = ', factorial(i), sep='')
Если бы глобальная переменная i изменялась внутри функции, то мы бы получили вот что:
5! = 1 5! = 2 5! = 6 5! = 24 5! = 120
Итак, если внутри функции модифицируется значение некоторой переменной, то переменная с таким именем становится локальной переменной, и ее модификация не приведет к изменению глобальной переменной с таким же именем.






Более формально: интерпретатор Питон считает переменную локальной для данной функции, если в её коде есть хотя бы одна инструкция, модифицирующая значение переменной, то эта переменная считается локальной и не может быть использована до инициализации. Инструкция, модифицирующая значение переменной — это операторы = , += , а также использование переменной в качестве параметра цикла for . При этом даже если инструкция, модицифицирующая переменную никогда не будет выполнена, интерпретатор это проверить не может, и переменная все равно считается локальной. Пример:
def f(): print(a) if False: a = 0 a = 1 f()
Возникает ошибка: UnboundLocalError: local variable 'a' referenced before assignment . А именно, в функции f() идентификатор a становится локальной переменной, т.к. в функции есть команда, модифицирующая переменную a , пусть даже никогда и не выполняющийся (но интерпретатор не может это отследить). Поэтому вывод переменной a приводит к обращению к неинициализированной локальной переменной.
Чтобы функция могла изменить значение глобальной переменной, необходимо объявить эту переменную внутри функции, как глобальную, при помощи ключевого слова global :
def f(): global a a = 1 print(a) a = 0 f() print(a)
В этом примере на экран будет выведено 1 1, так как переменная a объявлена, как глобальная, и ее изменение внутри функции приводит к тому, что и вне функции переменная будет доступна.






Тем не менее, лучше не изменять значения глобальных переменных внутри функции. Если ваша функция должна поменять какую-то переменную, пусть лучше она вернёт это значением, и вы сами при вызове функции явно присвоите в переменную это значение. Если следовать этим правилам, то функции получаются независимыми от кода, и их можно легко копировать из одной программы в другую.
Например, пусть ваша программа должна посчитать факториал вводимого числа, который вы потом захотите сохранить в переменной f. Вот как это не стоит делать:
def factorial(n): global f res = 1 for i in range(2, n + 1): res *= i f = res n = int(input()) factorial(n) # дальше всякие действия с переменной f
Этот код написан плохо, потому что его трудно использовать ещё один раз. Если вам завтра понадобится в другой программе использовать функцию «факториал», то вы не сможете просто скопировать эту функцию отсюда и вставить в вашу новую программу. Вам придётся поменять то, как она возвращает посчитанное значение.
Гораздо лучше переписать этот пример так:






# начало куска кода, который можно копировать из программы в программу def factorial(n): res = 1 for i in range(2, n + 1): res *= i return res # конец куска кода n = int(input()) f = factorial(n) # дальше всякие действия с переменной f
Если нужно, чтобы функция вернула не одно значение, а два или более, то для этого функция может вернуть список из двух или нескольких значений:
return [a, b]
Тогда результат вызова функции можно будет использовать во множественном присваивании:
Рекурсия в 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 сдвигается правее или левее, но сам массив остается неизменным.


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

Как настроить монитор по размеру экрана на виндовс 10
Как обновить сертификаты в браузере гугл хром
Как пользоваться termux на андроиде
Как скачать данные с самсунга на самсунг