Tail recursion – это такая рекурсия, когда вызов функцией самой себя происходит в самом конце. Такую рекурсию довольно просто разобрать на цикл, а циклы эффективнее по памяти, т.к. не требуют хранить и раскручивать весь стэк вызовов. Многие языки программирования имеют встроенную оптимизацию для такой рекурсии. Python – нет, но написать её крайне просто.
- Tail Recursion In Python – статья с простой реализацией через поднятие исключений.
- tco – довольно жирная реализация через исключения с кучей фич.
- pytailcall – 3 экспериментальных реализации через хакинг байткода. Немного деталей есть в статье. В ридми не написано, как это использовать, так что смотрите в бенчмарк
Реализацию без исключений (которые, к сожалению, довольно медленные) в виде пакета я нашёл, но лучше её не используйте, в ней есть некоторые проблемы.
Хвостовая рекурсия – кейс редкий, но довольно интересный, да. Have a fun :)