Python Language
Рекурсия
Поиск…
замечания
Рекурсия требует остановки stopCondition для выхода из рекурсии.
Первоначальная переменная должна быть передана рекурсивной функции, поэтому она будет сохранена.
Сумма чисел от 1 до n
Если бы я хотел узнать сумму чисел от 1 до n где n - натуральное число, я могу сделать 1 + 2 + 3 + 4 + ... + (several hours later) + n . В качестве альтернативы я мог бы написать цикл for :
n = 0
for i in range (1, n+1):
n += i
Или я мог бы использовать технику, известную как рекурсия:
def recursion(n):
if n == 1:
return 1
return n + recursion(n - 1)
Рекурсия имеет преимущества по сравнению с вышеприведенными двумя методами. Рекурсия занимает меньше времени, чем запись 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 наивная реализация факториальной операции может быть определена как функция следующим образом:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
Иногда функции рекурсии трудно схватить, поэтому давайте поэтапно пройдемся. Рассмотрим выражение 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 следующим образом:
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)
У вас может также быть несколько случаев рекурсии, но мы не будем вдаваться в это, потому что это относительно редко, и часто трудно мысленно обрабатывать.
Вы также можете иметь «параллельные» рекурсивные вызовы функций. Например, рассмотрим последовательность Фибоначчи, которая определяется следующим образом:
- Если число равно 0, то ответ равен 0.
- Если число равно 1, то ответ равен 1.
- В противном случае ответ представляет собой сумму двух предыдущих чисел Фибоначчи.
Мы можем определить это следующим образом:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
Я не буду проходить эту функцию так же тщательно, как и с factorial(3) , но окончательное значение возврата fib(5) эквивалентно следующему ( синтаксически недействительному) выражению:
(
fib((n - 2) - 2)
+
(
fib(((n - 2) - 1) - 2)
+
fib(((n - 2) - 1) - 1)
)
)
+
(
(
fib(((n - 1) - 2) - 2)
+
fib(((n - 1) - 2) - 1)
)
+
(
fib(((n - 1) - 1) - 2)
+
(
fib((((n - 1) - 1) - 1) - 2)
+
fib((((n - 1) - 1) - 1) - 1)
)
)
)
Это становится (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 можно относительно легко преобразовать в итеративный код следующим образом:
def factorial(n):
product = 1
while n > 1:
product *= n
n -= 1
return product
def fib(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
Обычно это самый эффективный способ ручного устранения рекурсии, но для более сложных функций может оказаться довольно сложным.
Другим полезным инструментом является декодер lru_cache Python, который можно использовать для уменьшения количества избыточных вычислений.
Теперь у вас есть идея о том, как избежать рекурсии в Python, но когда вы должны использовать рекурсию? Ответ «не часто». Все рекурсивные функции могут быть реализованы итеративно. Это просто вопрос, как это сделать. Однако есть редкие случаи, когда рекурсия в порядке. Рекурсия распространена в Python, когда ожидаемые входы не вызовут значительного количества вызовов рекурсивных функций.
Если рекурсия - это тема, которая вас интересует, я умоляю вас изучить функциональные языки, такие как Scheme или Haskell. На таких языках рекурсия гораздо более полезна.
Обратите внимание, что приведенный выше пример последовательности Фибоначчи, хотя он хорошо показывает, как применять определение в python и позже использовать кэш lru, имеет неэффективное время работы, так как он делает 2 рекурсивных вызова для каждого не базового случая. Количество вызовов функции растет экспоненциально до n .
Скорее неинтуитивно более эффективная реализация будет использовать линейную рекурсию:
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)
Но у этого есть вопрос о возвращении пары чисел. Это подчеркивает, что некоторые функции действительно не сильно выигрывают от рекурсии.
Исследование деревьев с рекурсией
Скажем, у нас есть следующее дерево:
root
- A
- AA
- AB
- B
- BA
- BB
- BBA
Теперь, если мы хотим перечислить все имена элементов, мы могли бы сделать это с помощью простого цикла for. Мы предполагаем, что существует функция get_name() чтобы вернуть строку имени узла, функцию get_children() чтобы вернуть список всех get_children() данного узла в дереве, а также функцию get_root() для получить корневой узел.
root = get_root(tree)
for node in get_children(root):
print(get_name(node))
for child in get_children(node):
print(get_name(child))
for grand_child in get_children(child):
print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA
Это работает хорошо и быстро, но что, если суб-узлы получили собственные узлы? И эти узлы могут иметь больше суб-узлов ... Что делать, если вы заранее не знаете, сколько их будет? Метод решения этой проблемы - использование рекурсии.
def list_tree_names(node):
for child in get_children(node):
print(get_name(child))
list_tree_names(node=child)
list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA
Возможно, вы не хотите печатать, но возвращаете плоский список всех имен узлов. Это можно сделать, передав список в качестве параметра.
def list_tree_names(node, lst=[]):
for child in get_children(node):
lst.append(get_name(child))
list_tree_names(node=child, lst=lst)
return lst
list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']
Увеличение максимальной глубины рекурсии
Существует предел глубине возможной рекурсии, которая зависит от реализации Python. Когда предел достигнут, возникает исключение RuntimeError:
RuntimeError: Maximum Recursion Depth Exceeded
Вот пример программы, которая вызовет эту ошибку:
def cursing(depth):
try:
cursing(depth + 1) # actually, re-cursing
except RuntimeError as RE:
print('I recursed {} times!'.format(depth))
cursing(0)
# Out: I recursed 1083 times!
Можно изменить предел глубины рекурсии, используя
sys.setrecursionlimit(limit)
Вы можете проверить, какие текущие параметры лимита выполняются:
sys.getrecursionlimit()
Выполняя тот же метод выше с нашим новым пределом, получим
sys.setrecursionlimit(2000)
cursing(0)
# Out: I recursed 1997 times!
Из Python 3.5 исключение представляет собой RecursionError, который получен из RuntimeError.
Рекурсия хвоста - плохая практика
Когда единственная вещь, возвращаемая функцией, является рекурсивным вызовом, она называется хвостовой рекурсией.
Вот пример обратного отсчета с использованием хвостовой рекурсии:
def countdown(n):
if n == 0:
print "Blastoff!"
else:
print n
countdown(n-1)
Любые вычисления, которые могут быть сделаны с использованием итерации, также могут быть выполнены с использованием рекурсии. Вот версия find_max, написанная с использованием хвостовой рекурсии:
def find_max(seq, max_so_far):
if not seq:
return max_so_far
if max_so_far < seq[0]:
return find_max(seq[1:], seq[0])
else:
return find_max(seq[1:], max_so_far)
Рекурсия хвоста считается плохой практикой в Python, поскольку компилятор Python не обрабатывает оптимизацию для хвостовых рекурсивных вызовов. Рекурсивное решение в таких случаях использует больше системных ресурсов, чем эквивалентное итеративное решение.
Оптимизация регенерации хвоста посредством интроспекции стека
По умолчанию рекурсивный стек Python не может превышать 1000 кадров. Это можно изменить, установив sys.setrecursionlimit(15000) который быстрее, однако этот метод потребляет больше памяти. Вместо этого мы также можем решить проблему рекурсии хвоста, используя интроспекцию стека.
#!/usr/bin/env python2.4
# This program shows off a python decorator which implements tail call optimization. It
# does this by throwing an exception if it is it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
This function fails if the decorated
function recurses in a non-tail context.
"""
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
Чтобы оптимизировать рекурсивные функции, мы можем использовать декоратор @tail_call_optimized для вызова нашей функции. Вот несколько примеров общей рекурсии с использованием декоратора, описанного выше:
Факториальный пример:
@tail_call_optimized
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
Пример Фибоначчи:
@tail_call_optimized
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.