Ты заметишь, что числа Фибоначчи растут очень быстро. Для int диапазон обычно до ~2 млрд, а числа Фибоначчи выходят за эти рамки уже к n ≈ 47. Поэтому для больших n лучше использовать long long или даже BigInteger в языках, где он есть.
Парадигма «Разделяй и властвуй»
Рекурсивный подход к Фибоначчи — пример метода «разделяй и властвуй»:
- Разделяем задачу на подзадачи (F(n−1), F(n−2)).
- Решаем подзадачи независимо.
- Объединяем результаты.
В дальнейшем мы будем встречать этот принцип в более сложных алгоритмах.
Формула Бине
Есть способ вычислить число Фибоначчи напрямую, без рекурсии:
Хотя формула всегда даёт целые значения при целых n, она использует вещественные числа, что снижает точность на больших n из-за ошибок округления.
import math
def fib_binet(n):
phi = (1 + math.sqrt(5)) / 2
return round((phi**n - (-phi)**(-n)) / math.sqrt(5))Важно: при больших n возможны ошибки округления из-за работы с вещественными числами.