Потому что этот алгоритм, будучи рализован в лоб без всяких кэшей и ускорителей, неоптимален! F(n–2) высчитывается дважды, F(n–3) трижды, F(n–4) пять раз, и т.д. по Фибоначчи.
Что читать, сказать не могу (в том издании Кормена, что у меня, маловато), гугли «динамическое программирование». Хотя поначалу поможет и Кормен.
ЗЫ. В некоторых случаях помогает вычисление в лоб, но с простеньким кэшем, который снизит повторяемость если не для всех входов, то хоть для самых вопиющих.
ЗЗЫ. Программисты не любят рекурсию по многим причинам. 1. Сложно наладить аварийный стоп. 2. Системный стек ограничен и есть риск переполнения.