Решение: Рекурсивный подсчёт звёздочек
Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.
Функция F(n) при $n > 0$ вызывает G(n − 1). Функция G(n) печатает символ «звёздочка», а при $n > 1$ вызывает F(n − 3).
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(18)?
Решение по шагам
4 шагаВызов F(n) при $n > 0$ передаёт управление функции G(n − 1). Функция G всегда печатает одну звёздочку.
$$f(n) = 1 + f(n - 4), \quad n > 2$$После вызова F(18) цепочка рекурсивных вызовов имеет аргументы:
$$18 \to 14 \to 10 \to 6 \to 2$$При F(2) вызывается G(1), которая печатает звёздочку. Условие $n > 1$ для G(1) не выполняется, поэтому дальнейших вызовов нет.
$$f(2)=1$$Суммируем по одному напечатанному символу на каждом уровне рекурсии.
$$f(18)=1+f(14)=1+1+f(10)=1+1+1+f(6)=1+1+1+1+f(2)=5$$Где здесь ошибаются
Учитывают только вызов G(1), забывая о звёздочках, напечатанных на предыдущих уровнях.
Уменьшают аргумент F на 3, хотя сначала F вызывает G с аргументом n − 1, а затем G вызывает F с аргументом n − 3; общий шаг равен 4.
Считают, что G печатает звёздочку только при условии $n > 1$.