Решение: Порядок рекурсивных вызовов
Ниже записан рекурсивный алгоритм $F$. При выполнении вызова $F(8)$ определите последовательность чисел, которые будут напечатаны на экране.
1def F(n): 2 if n > 0: 3 F(n - 4) 4 F(n // 2) 5 print(n)
Решение по шагам
5 шаговПри $n \leq 0$ функция ничего не выводит. При положительном $n$ сначала выполняется $F(n-4)$, затем $F(n \mathbin{//} 2)$, и только после этого выводится $n$.
Разберём вызов $F(1)$: оба рекурсивных вызова завершаются без вывода, затем печатается $1$.
$$F(1) \to 1$$Для $F(2)$ вызов $F(0)$ ничего не выводит, затем $F(1)$ выводит $1$, после чего печатается $2$.
$$F(2) \to 12$$Для $F(4)$ сначала вызывается $F(0)$, затем $F(2)$, после чего печатается $4$.
$$F(4) \to 124$$Вызов $F(8)$ дважды приводит к выводу последовательности $124$: сначала через $F(4)$, затем через $F(8 \mathbin{//} 2)=F(4)$. После этого печатается $8$.
$$F(8) \to 124\,124\,8$$Где здесь ошибаются
Выводят число до выполнения рекурсивных вызовов.
Учитывают вызовы с неположительным аргументом.
Забывают, что $F(4)$ вызывается внутри $F(8)$ дважды.