3 Что, как и когда рекурсии

Рекурсия происходит, когда вызов функции вызывает повторный вызов той же самой функции до завершения исходного вызова функции. Например, рассмотрят известное математическое выражение 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 .

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

  • Хвост вызов просто рекурсивный вызов функции , которая является последней операция должна быть выполнена перед возвратом значения. Для того, чтобы быть ясно, return foo(n - 1) является хвостом вызова, но return foo(n - 1) + 1 не является (так как добавление последняя операция).
  • Оптимизация хвостового вызова (TCO) является способом автоматического уменьшения рекурсии в рекурсивных функциях.
  • Устранение Хвост вызова (ТХЭ) является снижение хвоста вызова выражение , которое может быть оценено без рекурсии. TCE - это тип TCO.

Оптимизация 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)
 

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