Я тут один трюк с кэшированием разработал, он реально сокращает время работы рекурсивного поиска – практически до линейного. Не против, если вместе его разберем?

Вот как это делается: нужно сохранять результат каждой подзадачи при первом её возникновении, а потом просто извлекать его, вместо того, чтобы пересчитывать. В коде у меня словарь, где ключом выступают аргументы функции. И перед рекурсивным вызовом я проверяю кэш. Если ключ есть – возвращаю сохранённое значение, если нет – вычисляю, сохраняю и возвращаю. Так наивная экспоненциальная рекурсия превращается практически в линейное время для уникальных входных данных.

Да, я прогонял это через алгоритм поиска в глубину для лабиринта, где каждая ячейка может быть связана до четырех соседних. Ключом был кортеж, содержащий текущую позицию и множество посещенных ячеек. Разветвления были просто сумасшедшие – сотни тысяч путей, но после первого прохода кэш превратил оставшиеся рекурсивные вызовы в операции с постоянным временем, и общее время работы упало с минут до пары секунд. Важным моментом было эффективное хеширование посещенного множества с помощью frozenset, чтобы ключ оставался неизменным.