Решение: Рекурсивный подсчёт звёздочек
Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.
Функция F(n) при $n > 0$ вызывает функцию G(n − 1). Функция G(n) всегда печатает один символ «звёздочка», а при $n > 1$ вызывает функцию F(n − 3).
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(12)?
Решение по шагам
4 шагаВызов F(12) вызывает G(11), так как 12 > 0.
$$F(12) = G(11)$$Вызов G(11) печатает одну звёздочку и вызывает F(8), так как 11 > 1.
$$G(11) = 1 + F(8)$$Аналогично последовательно получаем вызовы G(7), F(4), G(3), F(0). Каждый из вызовов G печатает по одной звёздочке.
$$F(12) \to G(11) \to F(8) \to G(7) \to F(4) \to G(3) \to F(0)$$Вызов F(0) ничего не вызывает, поэтому рекурсия завершается. Функция G была вызвана три раза: G(11), G(7) и G(3).
$$1 + 1 + 1 = 3$$Где здесь ошибаются
Учитывать вызов F как печать звёздочки.
Продолжать рекурсию из F(0), хотя условие n > 0 не выполняется.
Забыть, что каждый вызов G печатает одну звёздочку до проверки условия n > 1.