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