Концепция рекурсии, которая в простейшем определении заключается в том, что функция вызывает сама себя, широко применяется в пространстве программирования, поскольку помогает разбивать большие сложные проблемы на более мелкие подзадачи, которые легче решать и чьи ответы можно объединять вместе. дать решение большей проблемы. Одним из наиболее часто встречающихся примеров функции рекурсии является вычисление факториала числа.
Как бы вы написали такую функцию на Python? Это может быть так же просто, как эти три строки:
Это рекурсивный вызов, и если мы более подробно рассмотрим, как компьютер обрабатывает рекурсию, мы знаем, что для каждого рекурсивного вызова будет создан стек и помещен в память. Этот стек содержит всю необходимую информацию, включая значения параметров функции. Когда функция завершается (т. е. вызывается базовый случай), информация выталкивается из из стека, и каждое значение в вызове возвращается, и, в конечном итоге, возвращается окончательное значение, как показано на этой диаграмме:
Здесь есть небольшая сложность, поскольку наша память ограничена — у нас нет неограниченных ресурсов, поэтому, если мы запускаем огромное количество рекурсивных вызовов, глубина стека становится очень большой, и мы можем достичь максимума пространства стека. Например, мы столкнемся с maximum recursion depth exceeded in comparison в Python при попытке найти факториал 10000 с помощью только что созданной функции.
Есть ли способ оптимизировать его, если мы все еще хотим использовать рекурсию? Да, существует такая концепция, которая называется Оптимизация хвостовой рекурсии. Функция является хвостовой рекурсией, если она заканчивается, возвращая значение рекурсивного вызова, тогда как если какая-либо дальнейшая обработка выполняется над возвращаемым значением рекурсивного вызова, функция не является хвостовой рекурсией. Например, в нашем случае значение factorial(n-1) используется для умножения n. Компьютеры умны, и если они знают, что мы больше ничего не будем делать с возвращаемым значением, они не будут добавлять еще один стек и повторно использовать существующий. Таким образом, теоретически мы не столкнемся с ошибкой maximum recursion depth exceeded in comparison при оптимизации хвостовой рекурсии.
Итак, как нам изменить нашу функцию, чтобы она оптимизировала хвостовую рекурсию? Сохранение промежуточного значения в качестве параметра может помочь в решении нашей проблемы:
Эта функция может быть именно тем, что нам нужно, за исключением того, что она не работает :(
В то время как некоторые языки программирования автоматически распознают и оптимизируют функцию хвостовой рекурсии, Python предпочитает иметь правильные обратные трассировки. Создатель языка Python Гвидо ван Россум также упомянул в двух своих блогах (ссылка и ссылка), как ему не нравится оптимизация хвостовой рекурсии. Он считает, что включение оптимизации хвостовой рекурсии может сбить с толку пользователей, которые непреднамеренно пишут что-то рекурсивное и нуждаются в отладке. Это также разные фундаментальные убеждения разных ученых-компьютерщиков. Я не буду комментировать высказанные здесь мнения, но я считаю, что нас всегда следует поощрять думать об оптимизации наших функций, а не просто о том, как заставить их работать, поэтому я провел небольшое исследование нескольких способов, которыми мы могли бы тактически реализовать хвост. рекурсию и представить здесь на случай, если читатели заинтересуются.
Во-первых, мы могли бы создать декоратор (концепцию декоратора в Python, пожалуйста, прочитайте здесь :) для нашей функции, чтобы оптимизировать хвостовой вызов.
Другой способ избежать ошибкиmaximum recursion depth exceeded in comparisonиспользовать итеративную функцию вместо рекурсивной.
Использованная литература:
https://stackoverflow.com/questions/27417874/tail-recursion-optimization-decorator-in-python
https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion
