Алгоритмы и рекурсия · тема 2 из 8
Рекурсия с базовым случаем
Рекуррентные функции · ЕГЭ 16
Одна идея — один пример
Рекурсия требует базового случая и движения к нему. Для F(n)=F(n-1)+n, F(0)=0 каждый вызов уменьшает n.
def f(n):
if n == 0: return 0
return f(n - 1) + n
print(f(3))Теперь решаем самостоятельно
cache сохраняет результаты повторных вызовов. Он не исправляет бесконечную рекурсию и не увеличивает допустимую глубину.
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Вводится n от 0 до 30. Выведи F(n), используя функцию с cache или итеративный алгоритм.
Пример входных данных и результата
Ввод:
0
Вывод:
0
Черновик и файл программы
Черновик сохраняется в этом браузере. Ctrl/⌘ + S — сохранить.
Результаты проверки
Напиши решение и нажми «Проверить код». Данные каждого теста подаются автоматически.
Нужна подсказка?
При n < 2 ответ равен n. Для остальных складываются два предыдущих.
На чём легко ошибиться
Рекурсия без cache пересчитывает одинаковые значения многократно.
Разобрать один из способов решения
Сначала попробуй написать код сам. Сравни алгоритм, затем закрой разбор и воспроизведи решение без подсказки.
from functools import cache
@cache
def f(n):
if n < 2: return n
return f(n - 1) + f(n - 2)
print(f(int(input())))Тесты проверяют результат на учебных примерах, но не доказывают правильность для любого входа. Объясни каждую строку и предложи собственный тест.
Перед следующей темой
Назови входные данные, результат, основной шаг алгоритма и граничный случай. Если использовал разбор, напиши решение заново. Для свободных экспериментов открой Python онлайн.
Все темы этого курса
Программа подготовлена по темам банка «Академии С». Официальные документы: ФИПИ. Справочник языка: Python. Не все экзаменационные задачи нужно решать программой: например, работа в таблицах требует освоения табличного редактора.