Дана рекурсивная функция на Python:
def f(n):
if n < 3:
return n
return f(n - 1) + 2 * f(n - 3)
Какое значение выведет программа после выполнения print(f(6))?
Показать ответ и разборСкрыть ответ и разбор
Верный ответ
- D12
Разбор
Базовый случай: при n < 3 функция возвращает n, поэтому f(0) = 0, f(1) = 1, f(2) = 2. Далее по формуле f(n) = f(n-1) + 2·f(n-3): f(3) = f(2) + 2·f(0) = 2 + 0 = 2; f(4) = f(3) + 2·f(1) = 2 + 2 = 4; f(5) = f(4) + 2·f(2) = 4 + 4 = 8; f(6) = f(5) + 2·f(3) = 8 + 4 = 12. Значение «8» — это f(5), «16» получается при ошибочном вызове f(n-2) вместо f(n-3), «18» получается, если принять f(0) = 1. Верно «12».