Числа Фибоначчи
Рекурсивно вычисляем числа Фибоначчи без циклов.
Как к ней подойти
Потренируйтесь выделять повторяющуюся логику в функцию и находить условие остановки рекурсии.
Функция получает аргументы и возвращает результат через return. Рекурсия разбивает задачу на меньшую такую же задачу; без базового случая вызовы не остановятся. Проверьте, что каждый шаг действительно приближает к нему.
pair возвращает F(n) и F(n+1). Формулы удвоения получают их из пары для n//2, поэтому число рекурсивных уровней мало.
Проверьте перед запуском
- Базовые случаи: F(0)=0, F(1)=1.
- Обычная рекурсия без кеша многократно считает одинаковые подзадачи.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Быстрое удвоение
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²) бит для сохранённых чисел.