Что такое хвостовая рекурсия и оптимизация хвостового вызова?
Введение
Рекурсия, которая происходит, когда функция вызывает сама себя, является базовой операцией в программировании. Распространенной проблемой является то, что рекурсия может исчерпать пространство стека, поскольку процесс рекурсии каждый раз создает новый кадр стека. В python при переполнении стека возникает ошибка «RecursionError: максимальная глубина рекурсии превышена при сравнении». Хвостовая рекурсия - это особый тип рекурсии, а оптимизация хвостового вызова - это метод, основанный на хвостовой рекурсии, чтобы избежать проблем с переполнением стека. Этот пост объяснит, что это такое и как они работают, на простом примере.
Объясните на примере
Давайте разберемся с ними на факториальном примере:
Факториальная функция - это традиционный метод рекурсии. На последнем этапе сначала вычисляется факториал (n-1), а затем умножается на n. Следовательно, нам нужно место для сохранения информации о текущей функции, чтобы вычислить окончательный результат после получения результата факториала (n-1).
Функция tailRecursionFactorial - это хвостовая рекурсия. По сравнению с традиционной рекурсией, в конце функции есть только один вызов, и, таким образом, не нужно сохранять информацию о вызывающем (текущая функция). Другими словами, на последнем шаге используется только результат tailRecursionFactorial (n - 1, acc * n), и никакая информация о текущей функции не будет использоваться снова после того, как мы получим результат tailRecursionFactorial (n - 1, в соотв. * П). Следовательно, вполне возможно использовать только один кадр стека для сохранения информации о функции, а не создавать новый кадр стека каждый раз при вызове функции. Эта идея называется оптимизацией хвостового вызова. Теоретически, эта оптимизация может уменьшить пространственную сложность процедуры рекурсии с линейной, или O (n), до мгновенной, или O (1). Это потрясающая сила хвостовой рекурсии!
Заключение
Уловка вышеупомянутой хвостовой рекурсии состоит в том, чтобы на самом деле использовать аккумулятор «acc» в качестве параметра функции для записи информации, поэтому нет необходимости что-либо делать (например, время n, как традиционный метод рекурсии done) после получения результата вызывающей функции.
К сожалению, язык Python не поддерживает оптимизацию хвостового вызова. Даже если вы напишете метод хвостовой рекурсии, он все равно будет работать как традиционная рекурсия, для которой требуется пространство O (n). Потому что Python предпочитает иметь правильную трассировку каждой функции, чтобы упростить процесс отладки.
Но не волнуйтесь, некоторые другие языки, такие как Scheme и другие, поддерживают оптимизацию хвостового вызова.
Спасибо за внимание. Если вам это нравится, следите за моей публикацией TechToFreedom, где вы можете ознакомиться с другими учебными пособиями по Python и статьями о программировании, технологиях и инвестициях.
