Решение: Рекурсивный подсчёт звёздочек
Ниже приведены две рекурсивные функции F и G. Функция F(n) вызывает G(n - 2), если n > 0. Функция G(n) печатает символ «*» и вызывает F(n - 1), если n > 1. Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(12)?
1def F(n): 2 if n > 0: 3 G(n - 2) 4 5def G(n): 6 print("*") 7 if n > 1: 8 F(n - 1)
Решение по шагам
5 шаговВызов $F(12)$ удовлетворяет условию $n > 0$, поэтому вызывается $G(10)$.
$$F(12) \to G(10)$$Функция $G(10)$ печатает одну звёздочку и вызывает $F(9)$.
$$G(10) \to F(9)$$Далее рекурсивные вызовы продолжаются по цепочке: $F(9) \to G(7) \to F(6) \to G(4) \to F(3) \to G(1)$.
Функция $G$ вызывается при аргументах 10, 7, 4 и 1. Каждый такой вызов печатает одну звёздочку. После $G(1)$ новый вызов $F$ не выполняется, так как условие $n > 1$ ложно.
Количество напечатанных символов равно числу вызовов функции $G$.
$$4 \cdot 1 = 4$$Где здесь ошибаются
Учитывать вызовы функции F как напечатанные символы.
Продолжать рекурсию после вызова G(1), хотя условие n > 1 ложно.
Ошибочно считать, что G печатает символ только при n > 1.