Числа Фибоначчи никогда рекурсией не считают. Это задачка первого курса программирования.
https://www.youtube.com/watch?v=OQ5jsbhAv_M
- Лекция в MIT по алгоритмам, в которой эта задача разбирается.
Это один из самых популярных вопросов на собеседованиях на позицию разработчика (за пределами России, понятно).