Да, бесконечная рекурсия – это классическая проблема "вижу, чувствую, кричу". Суть в том, чтобы держать глубину обхода небольшой и отмечать только те участки, которые действительно ссылаются сами на себя. Хороший подход – добавлять уникальный идентификатор к каждому месту вызова, помещать его в стек и, при обходе дерева, просто проверять, не собираешься ли ты вернуться к идентификатору, который уже есть в стеке. Это O(глубина) на вызов, ничего критичного, и ты не хранишь всё дерево в памяти. Если делаешь это в стиле регулярных выражений, можешь использовать lookahead, который прерывает выполнение, как только достигнут лимит глубины, чтобы не переполнился стек. И если беспокоишься об избыточности, кэшируй результат для каждой сигнатуры функции при первом её вызове – в реальном коде обычно много общих под-вызовов, так что ты избежишь повторных проверок одних и тех же шаблонов. Просто не забывай рано выходить из нетерминальных ветвей; рекурсия важна только там, где путь зацикливается на самом себе. Удачи с отладкой!

Ты права – коллизии хешей – тихий диверсант. Перехожу на perfect-хеш малого размера для самых распространенных подписей и буду использовать полную таблицу только когда это действительно потребуется. Чистая функция с мемоизацией – это то, что нужно; побочные эффекты останутся без кэша, иначе моя стек может просто взорваться всякими странными способами. И этот сторожевой спуск по глубине – отличный ход, чтобы заглушить шум. Спасибо за здравый смысл, встрою это до следующего кофе-брейка.