Цитата:
Рекурсия для Фибоначчи?
Без дополнительного кэширования полученных результатов?
И без дополнительных комментариев почему именно так?
мне бы тоже не понравилось.
Обычно подобные задачи решают рекурсивно на функциональных языках разработки с оптимизации хвостовой рекурсии. В этом случае стек не будет использоваться и его переполнения не произойдет. А кеширование достигается посредством memoization (не возьмусь сказать, как это называется на русском).
Если не ошибаюсь, подобная задача расбирается в одной из первых глав классической книги "Структура и интерпретация компьютернах программ".