Что такое рекурсия в питоне
Перейти к содержимому

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

  • автор:

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

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

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

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

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

Напомним, что в математике факториал числа 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

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

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

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

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

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

 
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.

Итоги

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

Для правильной работы она должна содержать базовый случай и передавать новому уровню рекурсии изменённые данные.

Информация обо всех незавершённых функциях хранится в стеке. При этом в каждый момент времени работает только та функция, которая находится наверху стека.

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

Читайте также:

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *