Задачи с рекурсивными алгоритмами
Понимание работы рекурсивного алгоритма традиционно вызывает определённые затруднения у школьников. Тем не менее, задача № 11, в которой выпускники должны продемонстрировать умения выполнить рекурсивный алгоритм, относится к базовому уровню сложности.
Рассмотрим задачу № 11 из демонстрационного варианта контрольно-измерительных материалов ЕГЭ 2015 года по информатике и ИКТ.
Задача №11. Ниже записан рекурсивный алгоритм F.
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
Решение.
- Печать значения параметра происходит всякий раз сразу после вызова функции F.
- Определим порядок рекурсивных вызовов. Для этого построим дерево, в узлах которого запишем значения параметра при вызове функции. В случае истинности условного выражения n < 5 происходит два рекурсивных вызова, поэтому строим бинарное дерево (см. рис. 1).
- Таким образом, искомая сумма определяется следующим образом:
3 • 5 + 2 • 7 + 2 • 4 + 6 + 3 + 2 + 1 = 49
Ответ. 49