Рекурсия в Python. Примеры решения задач
Рекурсия — это способ организации циклического процесса путем вызова рекурсивной функции. Рекурсивная функция — это функция, которая содержит код вызова самой себя с целью организации циклического процесса. С помощью рекурсивных функций можно с минимальным объемом кода решать некоторые задачи, обойдя использование (объявление) лишних структур данных. Рекурсию можно рассматривать как альтернативу циклам и итерациям.
2. Примеры решения задач на рекурсию
2.1. Функция CalcSumNumbers() . Вычислить сумму элементов набора чисел
В примере реализована рекурсивная функция CalcSumNumbers() , которая осуществляет суммирование чисел во входящем списке. В работе функции входящий список A разделяется на 2 части:
- первый элемент списка A[0] ;
- все остальные элементы списка кроме первого. Эти элементы выделяются при помощи среза A[1:] .
Вытащив первый элемент из списка с помощью среза, можно передать этот новосозданный список в следующий рекурсивный вызов функции.
здесь t – элемент, который проверяется с помощью функции isinstance() .
Нижеприведенная рекурсивная функция формирует ряд Фибоначчи в виде списка для заданного максимального значения в списке.
# Рекурсивная функция — возвращает ряд Фибоначчи в виде списка. # Параметр n — максимальное значение в списке. def GetFibonacciList (n, L): # Проверить, корректна ли длина списка count = len (L) if len (L)<2: return [] # Получить последние числа в списке L num1 = L[count-2] num2 = L[count-1] # Формула расчета следующего числа if (num1+num2) < n: L = L + [num1+num2] return GetFibonacciList(n, L) # вызвать рекурсивно функцию else : return L # если достигнут конец, то обычный выход # Вызвать функцию GetFibonacciList() LL = GetFibonacciList(100, [0, 1]) print ( «LL color: #333300;»>⇑
2.5. Функция ReverseNumber() . Реверсирование числа
В примере приводится функция ReverseNumber() представления числа в обратном порядке. Например, для числа 12345 результат будет 54321.
Функция получает входным параметром целое число number . Функция возвращает целое реверсированное число.
# Рекурсия. Реверсирование числа import math # Рекурсивная Функция def ReverseNumber (num): # 1. Проверка, корректно ли число if num<0: return -1 # 2. Проверка, равно ли число 0 if num==0: return 0 # 3. Если число корректно (num>0), то обработать его # 3.1. Определить порядок числа (количество цифр в числе) n_digit = 0 # порядок числа num2 = num # копия num while num2>0: n_digit = n_digit+1 num2 = num2//10 # 3.2. Взять последнюю цифру из числа t = num%10 # 123456 => 6 # 3.3. Умножить последнюю цифру на 10^n_digit res = t * int (math.pow(10, n_digit-1)) # 3.4. Вернуть сумму с вызовом рекурсивной функции return res + ReverseNumber(num//10) # Демонстрация использования функции num = 1234000567 rnum = ReverseNumber(num) # rnum = 7650004321 print ( «rnum color: #333300;»>⇑
2.6. Функция Power(x, y) . Возведение числа x в степень y
Рекурсивная функция Power(x, y) возвращает результат возведения действительного числа x в целую степень y . Предварительно предполагается, что значение y>0 .
# Рекурсия. Возведение числа x в степень y # Рекурсивная функция def Power (x, y): if y>0: return x * Power(x, y-1) else : return 1 # Демонстрация использования функции Power() x = 3 y = 4 res = Power(x, y) print ( «res color: #333300;»>⇑
2.7. Функция GetMaxList() . Определение максимального элемента списка
В примере реализована функция GetMaxList() , которая вычисляет максимальный элемент списка. Вся работа функции разделена на 2 части:
- выполнение действий, если в списке два и более чисел;
- выполнение действий, если список заканчивается, то есть рассматривается последний элемент.
Каждый рекурсивный вызов функции рассматривает список как две составляющие:
- первый элемент списка (элемент с индексом 0);
- следующие за первым элементы списка (элементы с индексами 1, 2, и т.д.).
# Рекурсивная функция. Определить максимальный элемент списка def GetMaxList (L): if len (L)>1: # Получить максимум из следующих рекурсивных вызовов Max = GetMaxList(L[1:]) # Сравнить максимум с первым элементом списка if L[0]<Max: return Max else : return L[0] if len (L)==1: # последний элемент в списке return L[0] # вернуть этот элемент # Демонстрация использования функции Power() L = [ 500, 2300, 800, 114, 36] res = GetMaxList(L) print ( «res color: #333300;»>⇑
2.8. Функция Convert_10_to_2() . Перевод из десятичной системи исчисления в двоичную
В данном примере, с целью сравнения, реализованы 2 функции, которые конвертируют целое число из десятичной системы исчисления в его аналог в двоичной системе исчисления:
- Convert_10_to_2_R() — это рекурсивная функция конвертирования числа;
- Convert_10_to_2() — не рекурсивная функция.
Для обеспечения решении задачи, в нерекурсивной версии Convert_10_to_2() вводится дополнительная переменная k , которая определяет порядок полученного двоичного числа. Для того, чтобы сохранять этот порядок k в рекурсивной версии функции Convert_10_to_2_R() , нужно его передавать в эту функцию вторым параметром.
Рекурсия в Python
Программирование и разработка
Рекурсия — одна из фундаментальных концепций информатики, она важна как для программистов, так и для специалистов по обработке данных. Мало того, что многие алгоритмы сортировки и поиска рекурсивны, но каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это отмечает, что рекурсия является ключевой концепцией, которую необходимо пересмотреть перед любым собеседованием по кодированию.
Сегодня мы поможем вам освежить свои навыки рекурсивного программирования на Python и рассмотрим 6 практических задач, чтобы получить практический опыт.
Что такое рекурсия?
Рекурсия — это концепция в информатике, когда функция вызывает саму себя и выполняет цикл до тех пор, пока не достигнет желаемого конечного условия. Он основан на математической концепции рекурсивных определений, которая определяет элементы в наборе с точки зрения других элементов в наборе.
Каждая рекурсивная реализация имеет базовый случай, когда желаемое состояние было достигнуто, и рекурсивный случай, когда желаемое состояние не было достигнуто, и функция переходит на другой рекурсивный шаг.
Поведение в рекурсивном случае перед вызовом рекурсивной функции, внутренний самовызов, повторяется на каждом шаге. Поэтому рекурсивные структуры полезны, когда вы можете решить более серьёзную проблему (базовый случай), выполнив повторяющиеся подзадачи (рекурсивный случай), которые постепенно перемещают программу к базовому случаю.
Это приводит к поведению, аналогичному циклам for или while, за исключением того, что рекурсия приближается к целевому условию, в то время как for циклы выполняются заданное количество раз, а while циклы выполняются до тех пор, пока условие больше не будет выполняться.
Другими словами, рекурсия декларативна, потому что вы устанавливаете состояние, которого хотите достичь, а for/ while циклы являются итеративными, потому что вам нужно установить количество повторений.
Как сочинять алгоритмы
— Космическая Энциклопедия. Звёздные дневники Ийона Тихого. Станислав Лем. косвенная рекурсия см. рекурсия косвенная. рекурсия см. рекурсия. рекурсия косвенная см. косвенная рекурсия.
Тема сегодняшнего занятия могла бы занимать год на серьёзном программистском факультете (но на ВМиК не занимает, размазывается тонким слоем по нескольким отдельным репликам в нескольких отдельных курсах и вообще сваливается на совесть отдельных личностей). На самом деле, тема тут даже не одна, а как минимум две: составление алгоритмов и оценка их сложности.
Я попробую впихнуть первое представление об этой теме в одно занятие, дабы дать первый вкус и, может, несколько простейших приёмов, и хотя бы установить какую-то терминологию.
The first rule of optimization
Но прежде, чем переходить к теме, я обязан познакомить вас с самым главным правилом: the first rule of optimization is: DON’T DO IT!.
Перевожу на русский: короткая и понятная функция лучше длинной и быстрой. Потому, узкое горлышко всё равно на практике окажется совсем не там, где вы оптимизировали.
Задача
Как водится, рассказы об алгоритмах я буду делать на примере подсчёта n-го элемента списка всех чисел Фибоначчи. (Сложилась в программировании такая традиция. Это и понятно: задача выглядит одновременно и достаточно просто, и имеет достаточно сложности, чтобы демонстрировать на ней много разных подходов).
Для начала вспомним (а кто не знает, узнаем) определение чисел Фибоначчи. Оно простое: первое и второе числа Фибоначчи – единицы; каждое следующее число Фибоначчи есть сумма двух предыдущих.
Пример 1: рекурсия (обратный проход, a.k.a. всплытие)
Если приглядеться, это определение уже очень похоже на обычную питоновскую рекурсию. Чуть-чуть подправим синтаксис так, чтобы получился питон, и получим:
Эта функция вызывает сама себя. Такой приём программирования называется рекурсия.
=== Как сочинять рекурсию ==
В общем случае рекурсивная функция будет выглядеть примерно так:
Стек вызовов
Посмотрим, как будет вычисляться эта функция. Для этого нам понадобится немного представления о том, как устроен интерпретатор питона.
Когда питон вызывает функцию, он создаёт у себя специальное место в памяти, где он запоминает: какую строчку функции он сейчас исполняет, и все значения локальных переменных функции. Соответственно, когда из этой функции мы вызываем ещё одну функцию, питон снова создаёт такое же место в памяти. Список всех таких мест в памяти называется стеком вызовов (стек от англ. stack – стопка; полное название: call stack или stack trace).
Стек вызовов легко наблюдать через дебаггер – там от стека отображается только имя функции и строка в ней, но если по нему щёлкнуть, то дебаггер показывает, какие локальные переменные хранятся на этом уровне стека.
Стек вызвов печатает питон при ошибке, чтобы объяснить, где же именно случилась ошибка. Эту картину вы уже наблюдали не один раз.
Обычно стэк изображают растущим сверху вниз или слева-направо (у нас он будет расти слева-направо, так удобнее).
Итак. Вызвали мы, например,
На внешнем уровне стэка у питона нет никаких переменных, он только знает, что он сейчас вычисляет fib1(4):
Погружаемся дальше. Первым делом питон создаёт по локальной переменной для каждого аргумента функции и присваивает в них значения:
Питон проверяет if, условие не выполняется, переходит в else:
Идём считать fib1(3):
При очередном вызове fib1 мы попали внутрь условия if, и наконец-то дошли до первого return, который мы можем выполнить:
Мы подставили значение из return вместо вызова, который к нему привёл, и свернули последний уровень стека. Но на вызове с n = 3 в return значение ещё не получено, снова нужно вызывать fib1:
Вот такое непростое дело – быть интерпретатором питона.
Если вы не понимаете, в чём у вас в программе ошибка, зачастую очень помогает представить себя интерпретатором питона и вот точно так же, как это сейчас изобразил я, повторить его работу.
Сложность алгоритма
Данная реализация функции хорошая и понятная, но у неё есть один недостаток: она _ОЧЕНЬ_ медленная.
Нетрудно посчитать, что функции fib(1) и fib(2) суммарно будут вызываться при такой реализации примерно fib(n) раз при вычислении значения fib(n). Ну а fib(n) ведёт себя асимптотически так же, как и e ** n. Историю про шахматную доску и экспоненту с n = 64 мы с вами помним.
Соответственно, если у нас нету априорных знаний, что эта функция будет вызываться только с небольшими n, наверное, такой реализации всё же лучше избегать. (Не переписывая ни буквы определения этой функции снаружи к ней можно приписать одну строчку так, чтобы для вычисления fib(n) она вызывала себя только n раз. Но об этом мы в этом семестре поговорить не успеем).
Так что попробуем изобрести что-нибудь другое.
Пример 2: кэширование
Получить вторую реализацию мы можем рассуждая двумя способами.
Способ размышления первый. Мы хотим всё-таки иметь соотношение, похожее на исходную постановку задачи. Мы выяснили уже, что если мы на каждом шагу делаем рекурсивный вызов, это плохо. И мы знаем из постановки задачи, что нам нужно использовать для n-го шага результаты с предыдущих шагов. Давайте тогда результаты с предыдущих шагов хранить в массиве, а основное отношение у нас приобретёт вид вычисления очередной ячейки массива по значениям двух других ячеек: fib[n] = fib[n - 1] + fib[n - 2]
Способ размышления второй. Попробуем сделать предыдущую реализацию всё-таки работающей не за экспоненту(n) шагов, а побыстрее. Мы видим, что у нас очень часто случаются вызовы с одним и тем же значением аргументов, и именно из-за этого вылезает плохая сложность функции. Давайте тогда складывать результаты вычисления функции для каждого аргумента в массив! Такой подход называется кэшированием.
Каким бы образом мы ни рассуждали, у нас получается вот такая реализация:
Ещё один приём программирования, на который я хочу обратить ваше внимание: мы сразу создали список нужной длины. В питоне нельзя присваивать за границы существующего списка (хотя есть конструкция append, и +=). В питоне нету никаких деклараций маиссивов или прочих конструкций, которые бы нас обязывали это делать. Но ведь всё, что нам нужно – это список длины n, заполненный каким-нибудь мусором. А это мы умеем, как раз это у нас делает range! (Можно было бы написать и более красиво: fibs = [1, 1] + [None] * (n - 2)>>. Заодно тут был бы элемент защиты от нашей собственной ошибки: если мы куда-то почему-то не записали значение, там будет <<
Ход вычисления
Ход вычисления тут очень простой. Посмотрим снова на примере
Демонстрирую это для того, чтобы показать, что почти всегда ход исполнения питонской программы – даже ход исполнения цикла for – можно свести к последовательности присваиваний в переменные. Это намекает нам на то, что можно придумать удобный формат записи хода исполнения нерекурсивных функций: просто писать последовательность присваиваний. Покуда у нас нет сложной рекурсии, всё, что нас интересует, происходит на одном уровне стека.
Пример 3: рекурсия (прямой проход, a.k.a. погружение)
Посмотрим снова на пример 1. Основное действие у него происходит тут: return fib(n - 1) + fib(n - 2). Т.е. мы до рекурсивного вызова считаем новые значения n, делаем два рекурсивных вызова, и только на возврате из рекурсии считаем, наконец, результат вычисления функции.
Иногда это бывает плохой идеей и хочется результат очередного шага рекурсии считать до рекурсивного вызова. Такой подход называется работой на прямом проходе рекурсии. (В данном случае этот пример носит определённо извращенческий характер, и разве что показывает разнообразие возможных подходов к одной и той же простой задаче).
Итак, мы решили работать на прямом проходе. Следовательно, нам придётся ввести вспомогательную функцию, которая будет делать собственно саму рекурсию: у этой функции будет больше аргументов, чтобы для шага рекурсии было достаточно данных.
Тут у нас возникает сложная задача: на какой вопрос будет отвечать наша вспомогательная функция? Для самой нашей функции вопрос известен: она получает n и отвечает на вопрос, каким будет n-е число Фибоначчи. Для вспомогательной функции я предлагаю такую постановку вопроса: она получает n, первое число Фибоначчи, второе число Фибоначчи, и отвечает на вопрос, каким будет n-е число Фибоначчи за ними.
Логика довольно проста. Нам даны первое и второе числа. Соответственно, для n == 1 и n == 2 мы ответ сразу знаем: для 1 это a, для 2 это b. (Красоты и понятности ради, я убрал условие для n == 2: оно нам и не потребуется).
Если же мы ответа не знаем сразу, то из двух текущих чисел Фибоначчи мы можем посчитать два следующих.
Дословно это в примере и написано. Оставляю читателю в качестве задачи убедиться, что эта функция работает правильно.
Пример 4: цикл с запоминанием
Очередной подход кажется очень похожим на пример 2, но демонстрирует совсем другую идею.
В питоне есть большое количество объектов, которые ведут себя примерно как список – их содержимое можно перебирать циклом for, – но списком они не являются – у них нельзя попросить i-й элемент. Пока что мы на такие объекты не натыкались, но скоро наткнёмся. Когда мы работаем с такого рода объектом, и нам нужно описать алгоритм, который учитывает не только очередной элемент, но и его соседей, всё, что мы можем сделать – это запоминать значения с предыдущих итераций.
Вот как это будет выглядеть на примере чисел Фибоначчи:
Здесь в основной части тела цикла (т.е. внутри if) prev – значение fib с предыдущей итерации, а pprev – с пред-предыдущей.
if можно переписать покрасивее: if None not in [prev, pprev].
Ещё можно сменить точку зрения на то, что же именно мы считаем предыдущим и пред-предыдущим значениями: мы знаем первые два значения, поэтому мы можем вместо того, чтобы заполнять переменные изначально None, заполнить их сразу содрежательными значениями, избавиться от условия в теле цикла, и делать на две итерации меньше, лишь бы не ошибиться с тем, что мы возвращаем:
Как я уже объяснил, иногда использование такого подхода в питоне оказывается неизбежным.
Кроме этого, основное его достоинство в оптимальности: мы не заводим лишних больших массивов (оптимизация по объёму памяти), мы не делаем большого количества дорогостоящих операций и работаем в линейное время (оптимизация по времени). Но это тот самый случай, против которого я предупреждал: optimization: DON'T DO IT. Хранение предыдущего шага итерации зачастую оказывается довольно неочевидным для читателя, провоцирует к ошибкам (если мы не в тот момент сохраняем предыдущее значение, полезут ошибки, которые бывает трудно выловить), а если нам приходится хранить больше одного значения с предыдущей итерации, то почвы для ошибок становится ещё больше и требуется крайняя внимательность при программировании.
Мудрый программист знает, что он невнимателен, и использует те подходы, которые требуют от него меньше умственных усилий и защищают его от собственных ошибок.
Python Language
Рекурсия
report this ad
Рекурсия требует остановки stopCondition для выхода из рекурсии.
Первоначальная переменная должна быть передана рекурсивной функции, поэтому она будет сохранена.
Сумма чисел от 1 до n
Если бы я хотел узнать сумму чисел от 1 до n где n - натуральное число, я могу сделать 1 + 2 + 3 + 4 + . + (several hours later) + n . В качестве альтернативы я мог бы написать цикл for :
Или я мог бы использовать технику, известную как рекурсия:
Рекурсия имеет преимущества по сравнению с вышеприведенными двумя методами. Рекурсия занимает меньше времени, чем запись 1 + 2 + 3 для суммы от 1 до 3. Для recursion(4) рекурсия может использоваться для обратной работы:
Функциональные вызовы: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)
В то время for цикл for работает строго вперед: (1 -> 1 + 2 -> 1 + 2 + 3 -> 1 + 2 + 3 + 4 -> 10). Иногда рекурсивное решение проще, чем итеративное решение. Это очевидно при реализации обращения к связанному списку.
Что, как и когда рекурсия
Рекурсия происходит, когда вызов функции вызывает повторение той же функции до того, как завершение вызова функции функции завершается. Например, рассмотрим известное математическое выражение x! (т.е. факториальной операции). Факториальная операция определена для всех неотрицательных целых чисел следующим образом:
- Если число равно 0, то ответ равен 1.
- В противном случае ответ заключается в том, что число раз факториал одного меньше, чем это число.
В Python наивная реализация факториальной операции может быть определена как функция следующим образом:
Иногда функции рекурсии трудно схватить, поэтому давайте поэтапно пройдемся. Рассмотрим выражение factorial(3) . Это и все вызовы функций создают новую среду . Среда в основном представляет собой таблицу, которая сопоставляет идентификаторы (например, n , factorial , print и т. Д.) С их соответствующими значениями. В любой момент времени вы можете получить доступ к текущей среде с помощью locals() . В первом вызове функции единственная локальная переменная, которая определяется, равна n = 3 . Поэтому печать locals() будет показывать <'n': 3>. Так как n == 3 , возвращаемое значение становится n * factorial(n - 1) .
На этом следующем этапе ситуация может немного запутаться. Глядя на наше новое выражение, мы уже знаем, что такое n . Однако мы еще не знаем, что такое factorial(n - 1) . Во-первых, n - 1 оценивается до 2 . Затем 2 передается factorial как значение для n . Поскольку это новый вызов функции, создается вторая среда для хранения этого нового n . Пусть A - первое окружение, а B - второе окружение. A все еще существует и равен <'n': 3>, однако B (что равно <'n': 2>) является текущей средой. Глядя на тело функции, возвращаемое значение, опять же, n * factorial(n - 1) . Не оценивая это выражение, заменим его на исходное выражение return. Делая это, мы мысленно отбрасываем B , поэтому не забудьте заменить n соответственно (т.е. ссылки на B n заменены на n - 1 который использует A n ). Теперь исходное обратное выражение становится n * ((n - 1) * factorial((n - 1) - 1)) . Сделайте секунду, чтобы понять, почему это так.
Теперь давайте оценим factorial((n - 1) - 1)) . Так как A n == 3 , мы переходим 1 к factorial . Поэтому мы создаем новую среду C, которая равна <'n': 1>. Опять же, возвращаемое значение n * factorial(n - 1) . Итак, заменим factorial((n - 1) - 1)) выражения «original» return аналогично тому, как раньше мы скорректировали исходное выражение return. «Оригинальное» выражение теперь n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .
Почти сделано. Теперь нам нужно оценить factorial((n - 2) - 1) . На этот раз мы пройдем 0 . Следовательно, это оценивается в 1 . Теперь давайте проведем нашу последнюю замену. «Оригинальное» выражение возврата теперь n * ((n - 1) * ((n - 2) * 1)) . Напомнив, что исходное выражение возврата оценивается под A , выражение становится 3 * ((3 - 1) * ((3 - 2) * 1)) . Это, конечно, оценивается до 6. Чтобы подтвердить, что это правильный ответ, напомните, что 3! == 3 * 2 * 1 == 6 . Прежде чем читать дальше, убедитесь, что вы полностью понимаете концепцию среды и то, как они применяются к рекурсии.
Утверждение, if n == 0: return 1 , называется базовым. Это потому, что он не рекурсии. Требуется базовый корпус. Без этого вы столкнетесь с бесконечной рекурсией. С учетом сказанного, если у вас есть хотя бы один базовый случай, у вас может быть столько случаев, сколько вы хотите. Например, мы могли бы эквивалентно записать factorial следующим образом:
У вас может также быть несколько случаев рекурсии, но мы не будем вдаваться в это, потому что это относительно редко, и часто трудно мысленно обрабатывать.
Вы также можете иметь «параллельные» рекурсивные вызовы функций. Например, рассмотрим последовательность Фибоначчи, которая определяется следующим образом:
- Если число равно 0, то ответ равен 0.
- Если число равно 1, то ответ равен 1.
- В противном случае ответ представляет собой сумму двух предыдущих чисел Фибоначчи.
Мы можем определить это следующим образом:
Я не буду проходить эту функцию так же тщательно, как и с factorial(3) , но окончательное значение возврата fib(5) эквивалентно следующему ( синтаксически недействительному) выражению:
Это становится (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) который, конечно, оценивается до 5 .
Теперь давайте рассмотрим еще несколько терминов словаря:
- Хвост вызова - это просто вызов рекурсивной функции, который является последней операцией, которая должна быть выполнена перед возвратом значения. Чтобы быть ясным, return foo(n - 1) является хвостовым вызовом, но return foo(n - 1) + 1 не является (поскольку добавление является последней операцией).
- Оптимизация звонков (TCO) - это способ автоматического сокращения рекурсии в рекурсивных функциях.
- Устранение хвостового вызова (TCE) - это сокращение хвостового вызова до выражения, которое может быть оценено без рекурсии. TCE - тип TCO.
Оптимизация звонков может быть полезной по нескольким причинам:
- Интерпретатор может минимизировать объем памяти, занятой средами. Поскольку ни один компьютер не имеет неограниченной памяти, чрезмерные рекурсивные вызовы функций приведут к переполнению стека .
- Интерпретатор может уменьшить количество переключателей кадров стека .
Python не имеет формы TCO, реализованной по ряду причин . Поэтому для ограничения этого ограничения необходимо использовать другие методы. Метод выбора зависит от варианта использования. С некоторой интуицией определения factorial и fib можно относительно легко преобразовать в итеративный код следующим образом:
Обычно это самый эффективный способ ручного устранения рекурсии, но для более сложных функций может оказаться довольно сложным.
Другим полезным инструментом является декодер lru_cache Python, который можно использовать для уменьшения количества избыточных вычислений.
Теперь у вас есть идея о том, как избежать рекурсии в Python, но когда вы должны использовать рекурсию? Ответ «не часто». Все рекурсивные функции могут быть реализованы итеративно. Это просто вопрос, как это сделать. Однако есть редкие случаи, когда рекурсия в порядке. Рекурсия распространена в Python, когда ожидаемые входы не вызовут значительного количества вызовов рекурсивных функций.
Если рекурсия - это тема, которая вас интересует, я умоляю вас изучить функциональные языки, такие как Scheme или Haskell. На таких языках рекурсия гораздо более полезна.
Обратите внимание, что приведенный выше пример последовательности Фибоначчи, хотя он хорошо показывает, как применять определение в python и позже использовать кэш lru, имеет неэффективное время работы, так как он делает 2 рекурсивных вызова для каждого не базового случая. Количество вызовов функции растет экспоненциально до n .
Скорее неинтуитивно более эффективная реализация будет использовать линейную рекурсию:
Но у этого есть вопрос о возвращении пары чисел. Это подчеркивает, что некоторые функции действительно не сильно выигрывают от рекурсии.
Исследование деревьев с рекурсией
Скажем, у нас есть следующее дерево:
Теперь, если мы хотим перечислить все имена элементов, мы могли бы сделать это с помощью простого цикла for. Мы предполагаем, что существует функция get_name() чтобы вернуть строку имени узла, функцию get_children() чтобы вернуть список всех get_children() данного узла в дереве, а также функцию get_root() для получить корневой узел.
Это работает хорошо и быстро, но что, если суб-узлы получили собственные узлы? И эти узлы могут иметь больше суб-узлов . Что делать, если вы заранее не знаете, сколько их будет? Метод решения этой проблемы - использование рекурсии.
Возможно, вы не хотите печатать, но возвращаете плоский список всех имен узлов. Это можно сделать, передав список в качестве параметра.
Увеличение максимальной глубины рекурсии
Существует предел глубине возможной рекурсии, которая зависит от реализации Python. Когда предел достигнут, возникает исключение RuntimeError:
Вот пример программы, которая вызовет эту ошибку:
Можно изменить предел глубины рекурсии, используя
Вы можете проверить, какие текущие параметры лимита выполняются:
Выполняя тот же метод выше с нашим новым пределом, получим
Из Python 3.5 исключение представляет собой RecursionError, который получен из RuntimeError.
Рекурсия хвоста - плохая практика
Когда единственная вещь, возвращаемая функцией, является рекурсивным вызовом, она называется хвостовой рекурсией.
Вот пример обратного отсчета с использованием хвостовой рекурсии:
Любые вычисления, которые могут быть сделаны с использованием итерации, также могут быть выполнены с использованием рекурсии. Вот версия find_max, написанная с использованием хвостовой рекурсии:
Рекурсия хвоста считается плохой практикой в Python, поскольку компилятор Python не обрабатывает оптимизацию для хвостовых рекурсивных вызовов. Рекурсивное решение в таких случаях использует больше системных ресурсов, чем эквивалентное итеративное решение.
Оптимизация регенерации хвоста посредством интроспекции стека
По умолчанию рекурсивный стек Python не может превышать 1000 кадров. Это можно изменить, установив sys.setrecursionlimit(15000) который быстрее, однако этот метод потребляет больше памяти. Вместо этого мы также можем решить проблему рекурсии хвоста, используя интроспекцию стека.
Чтобы оптимизировать рекурсивные функции, мы можем использовать декоратор @tail_call_optimized для вызова нашей функции. Вот несколько примеров общей рекурсии с использованием декоратора, описанного выше: