Рекурсия в Python

Сумма чисел от 1 до n

Если бы я хотел узнать сумму чисел от 1 до n, где n — натуральное число, я мог бы посчитать вручную 1 + 2 + 3 + 4 + ... + (несколько часов спустя) + 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.

Для recusion(4) рекурсия может работать в обратную сторону:

Вызов функций: (4 -> 4 + 3 -> 4 + 3 + 2 -> 4 + 3 + 2 + 1 -> 10)

Принимая во внимание, что цикл [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)) выражения return аналогично тому, как раньше мы скорректировали исходное выражение return. Исходное выражение теперь n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))).

Почти закончили. Теперь нам нужно оценить factorial((n - 2) - 1). На этот раз мы пропустим через 0.  Следовательно, должно получиться 1.

Теперь давайте проведём нашу последнюю замену. Исходное выражение return теперь n * ((n - 1) * ((n - 2) * 1)). Напомню, что исходное выражение возврата оценивается под A , выражение становится 3 * ((3 - 1) * ((3 - 2) * 1)). Здесь получается 6.

Чтобы убедиться, что это правильный ответ, вспомните, что 3! == 3 * 2 * 1 == 6. Прежде чем читать дальше, убедитесь, что вы полностью понимаете концепцию среды и то, как они применяются к рекурсии.

Утверждение, if n == 0: return 1, называется базовым случаем. Потому что это не рекурсия. Базовый случай необходим, без него вы столкнетесь с бесконечной рекурсией. С учетом сказанного, если у вас есть хотя бы один базовый случай, у вас может быть столько случаев, сколько вы хотите. Например, можно записать факториал  таким образом:

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.

Теперь давайте рассмотрим еще несколько терминов:

Tail call  — это просто вызов рекурсивной функции, который является последней операцией и должна быть выполнена перед возвратом значения. Чтобы было понятно, return foo(n - 1) — это хвост вызова, но return foo(n - 1) + 1 не является (поскольку операция сложения будет последней операцией).

Оптимизация хвоста вызова (TCO или tail cost optimization) — это способ автоматического сокращения рекурсии в рекурсивных функциях.

Устранение хвоста вызова (TCE или tail cost elimination) - это сокращение хвостового вызова до выражения, которое может быть оценено без рекурсии. 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, когда ожидаемые вводы не вызовут значительного количества вызовов рекурсивных функций.

Если вы интересуетесь рекурсией, стоит изучить функциональные языки, такие как 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_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))
# Выводит: 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))
# Выводит: 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 не превышает 1000 кадров. Это ограничение можно изменить, установив sys.setrecursionlimit(15000) который быстрее, однако этот метод потребляет больше памяти. Вместо этого мы также можем решить проблему рекурсии хвоста, используя интроспекцию стека.

#!/usr/bin/env python2.4
# Эта программа показыает работу декоратора, который производит оптимизацию хвостового вызова. Он делает это, вызывая исключение, если оно является его прародителем, и перехватывает исключения, чтобы вызвать стек.

import sys

class TailRecurseException:
  def __init__(self, args, kwargs):
  	self.args = args
    self.kwargs = kwargs

# Эта программа показыает работу декоратора, который производит
# оптимизацию хвостового вызова. Он делает это, вызывая исключение, если
# оно является его прародителем, и перехватывает исключения, чтобы
# подделать оптимизацию хвоста Эта функция не работает, если функция
# декоратора возвращается без хвоста.

def tail_call_optimized(g):
  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 as e:
            args = e.args
            kwargs = e.kwargs
  func.__doc__ = g.__doc__
  return func

Чтобы оптимизировать рекурсивные функции, мы можем использовать декоратор @tail_call_optimized для вызова нашей функции. Вот несколько примеров общей рекурсии с использованием декоратора, описанного выше:

Факториальный пример:

#  "calculate a factorial"

@tail_call_optimized
def factorial(n, acc=1):
  if n == 0:
    return acc
  return factorial(n-1, n*acc)

print(factorial(10000))
# печатает очень большое число
# и не достигает лимита рекурсии.

Пример Фибоначчи:
@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))
# также выводит большое число,
# но не доходит до лимита рекурсии

Чтобы выйти из рекурсии, нужно ввести команду stopCondition.

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