Числа Фибоначчи
Вы решили задачу. Теперь можно сравнить подходы.
Рекурсивно вычисляем числа Фибоначчи без циклов.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Быстрое удвоение
pair возвращает F(n) и F(n+1). Формулы удвоения получают их из пары для n//2, поэтому число рекурсивных уровней мало.
def pair(n):
if n == 0:
return 0, 1
a, b = pair(n // 2)
c = a * (2 * b - a)
d = a * a + b * b
return (d, c + d) if n % 2 else (c, d)
def fib(n):
return pair(n)[0]
print(fib(int(input())))
Время: O(log(n + 1)) арифметических операций над растущими целыми. Память: O(log(n + 1)) кадров и O(n) бит чисел Фибоначчи.
Другой способ: Рекурсия с запоминанием
Сохраняем результат каждого аргумента и используем определение F(n)=F(n−1)+F(n−2). Для больших n ограничение глубины рекурсии делает этот вариант менее подходящим.
from functools import lru_cache
@lru_cache(None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(int(input())))
Время: O(n) сложений больших целых. Память: O(n) записей и кадров; суммарно O(n²) бит для сохранённых чисел.
На что обратить внимание
- Базовые случаи: F(0)=0, F(1)=1.
- Обычная рекурсия без кеша многократно считает одинаковые подзадачи.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.