Решение: Порядок рекурсивных вызовов
Ниже на пяти языках программирования записан рекурсивный алгоритм $F$. При $n > 0$ алгоритм сначала выводит значение $n$, затем вызывает $F(n - 4)$, а после этого — $F(\lfloor n/2 \rfloor)$. Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова $F(8)$. Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Решение по шагам
4 шагаПри вызове $F(8)$ сначала выводится число $8$. Затем выполняются вызовы $F(4)$ и $F(4)$.
$$F(8) \to 8,\ F(4),\ F(4)$$Первый вызов $F(4)$ выводит $4$, затем вызывает $F(0)$ и $F(2)$. Вызов $F(0)$ ничего не выводит, а $F(2)$ выводит $2$, после чего вызывает $F(-2)$ и $F(1)$.
Вызов $F(1)$ выводит $1$, а его дальнейшие вызовы имеют неположительные аргументы и ничего не выводят. Поэтому один вызов $F(4)$ даёт последовательность $421$.
Второй вызов $F(4)$ даёт такую же последовательность $421$.
Где здесь ошибаются
Забывают, что после завершения первого рекурсивного вызова выполняется второй.
Выводят число после рекурсивных вызовов, хотя оно печатается до них.
Учитывают вызовы с неположительными аргументами, хотя условие вывода — $n > 0$.