1
Этап 1. Базовая задача
Практика1. Задача: Реализовать вычисление n-го числа Фибоначчи классическим способом через рекурсию
def fib(n: int) -> int:
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)2. Что такое рекурсия?
3. Каковы базовые условия выхода из рекурсии?
4. Как устроен стек вызовов?
2
Этап 2. Тестирование и первая проблема
5. Почему функция вычисления чисел Фибоначчи на больших n падает с ошибкой?
3
Этап 3. Анализ сложности
Вопрос
6. Какова временная сложность рекурсивного алгоритма для чисел Фибоначчи?
Ответ
O(2^n) из-за экспоненциального роста повторных вычислений.
Вопрос
7. Какова пространственная сложность рекурсивного алгоритма?
Ответ
O(n) из-за глубины стека рекурсии.
4