16 номер. Рекурсия
Рекурсивная процедура и вывод
Определите сумму чисел, которые выведет процедура при вызове F(30).
def F(n): print(n+1) if n>1: print(n+5) F(n-1) F(n-2)Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
Искомая величина: Определите сумму чисел, которые выведет процедура при вызове F(30).
Процедура печатает значения, поэтому её результат нужно описать отдельной функцией: C(n) — число напечатанных символов либо S(n) — сумма напечатанных чисел, в зависимости от вопроса. Возвращаемое значение самой процедуры для этого не используется.
Разберите один вызов по коду. Учитывайте печать до условия, внутри выполненной ветви и после неё. При невыполненном условии рекурсивных вызовов может не быть, но безусловная печать всё равно выполняется — это определяет базовый случай.
К собственному вкладу вызова прибавьте вклады всех рекурсивных вызовов с аргументами из программы. Одинаковый под-вызов учитывается столько раз, сколько он выполняется. Для числа символов или суммы порядок печати не меняет итог; при вопросе о порядке вывода его нужно сохранить.
Вычисляйте полученную вспомогательную функцию с сохранением уже найденных значений. Кэшируйте количество или сумму, а не саму печатающую процедуру: кэширование процедуры пропустит повторную печать и изменит ответ.
Ответ: 19997545.