Шешімі: Рекурсивный алгоритм F
Ниже на пяти языках программирования записан рекурсивный алгоритм $F$:
если $n > 2$, то последовательно выполняются вызовы $F(n - 1)$ и $F(n \mathbin{//} 2)$, после чего выводится значение $n$. Здесь $\mathbin{//}$ обозначает целочисленное деление.
Определите порядок вывода чисел при выполнении вызова $F(7)$.
Запишите подряд без пробелов и разделителей все числа в том порядке, в котором они выводятся на экран.
Шешім по шагам
5 қадамВызов $F(7)$ сначала запускает $F(6)$, затем $F(3)$, а число $7$ выводится последним.
$$F(7) \to F(6),\ F(3),\ 7$$Разбираем вызов $F(6)$: сначала выполняется $F(5)$, затем $F(3)$, после чего выводится $6$.
$$F(6) \to F(5),\ F(3),\ 6$$Вызов $F(5)$ даёт $F(4)$ и $F(2)$. Вызов $F(2)$ ничего не выводит, поэтому сначала получаем результат $F(4)$, затем выводится $5$.
$$F(5) \to F(4),\ F(2),\ 5$$Вызов $F(4)$ даёт $F(3)$ и $F(2)$, после чего выводится $4$. Вызов $F(3)$ выводит $3$, так как оба его рекурсивных вызова имеют аргументы, не превышающие 2.
$$F(3) \to 3;\quad F(4) \to 3,4$$Следовательно, $F(6)$ выводит $345363$, а весь вызов $F(7)$ — $345363$, затем $3$, затем $7$.
$$345363 + 3 + 7 = 3453637$$Где здесь ошибаются
Выводят число до выполнения рекурсивных вызовов.
Забывают, что вызовы выполняются слева направо: сначала $F(n-1)$, затем $F(n \mathbin{//} 2)$.
Учитывают вывод для аргументов $n \leq 2$, хотя условие рекурсии при них не выполняется.