Рекурсия в Python

Введение

Примеры

  • Сумма чисел от 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 цикла работает строго вперед: (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 . Пусть А первая среда и B будет вторая среда. Еще существует и равен {'n': 3} , однако, В (который равен {'n': 2} ) является текущая среда. Глядя на тело функции, возвращаемое значение, опять же , n * factorial(n - 1) . Не оценивая это выражение, давайте подставим его в исходное возвращаемое выражение. Делая это, мы мысленно отбрасывая B, так что не забудьте заменить n соответственно (то есть ссылки на B «s n заменяются n - 1 , который использует» s n ). Теперь, исходное выражение возвращение становится n * ((n - 1) * factorial((n - 1) - 1)) . Потратьте секунду, чтобы убедиться, что вы понимаете, почему это так.

    Теперь, давайте оценивать factorial((n - 1) - 1)) часть этого. Так как A «s n == 3 , мы передаем 1 в factorial . Таким образом, мы создаем новую среду C , которая равна {'n': 1} . Опять же , возвращаемое значение равно n * factorial(n - 1) . Итак , давайте заменить factorial((n - 1) - 1)) от «оригинала» вернуть выражения аналогично тому , как мы скорректировали первоначальное возвращение выражением ранее. «Оригинальный» выражение теперь n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))) .

    Почти сделано. Теперь нам нужно оценить factorial((n - 2) - 1) . На этот раз, мы проходим в 0 . Таким образом, это имеет значение 1 . Теперь давайте выполним нашу последнюю замену. «Оригинал» вернуть выражение теперь n * ((n - 1) * ((n - 2) * 1)) . Ссылаясь , что исходное выражение возвращаемый вычисляется в соответствии с А, выражение становится 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 .

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

    Оптимизация Tail Call полезна по ряду причин:

    • Интерпретатор может минимизировать объем памяти, занимаемый средами. Так как ни один компьютер не имеет неограниченную память, избыточные вызовы рекурсивных функций могут привести к переполнению стека .
    • Интерпретатор может уменьшить количество кадре стека коммутаторов.

    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
    
     

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

    Еще один полезный инструмент в Python 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))
    # 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) , который быстрее , однако, этот метод потребляет больше памяти. Вместо этого мы также можем решить проблему Tail Recursion, используя интроспекцию стека.

    #!/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. 

Синтаксис

Параметры

Примечания