Задание EGEINF82EE49: Рекурсия и рекуррентные зависимости

Начальный вызов: F(7). Нужно записать все напечатанные числа в порядке вывода, без разделителей.

Рекурсивный вызов выполняется полностью, прежде чем программа продолжит следующую строку вызывающей процедуры. Поэтому порядок команд существенен. При завершении вызова возвращаемся к месту его вызова; уже напечатанные символы сохраняются. Одинаковые вызовы в разных местах выполняются каждый раз и не объединяются.

Процедура F: при n ≥ 3 последовательно выполняются печать n, затем вызов F(n − 1), затем вызов F(⌊n2⌋).

Запись ⌊nd⌋ означает целую часть частного. Здесь деление выполняется при положительном n, поэтому дробная часть просто отбрасывается. Такой аргумент вычисляется до начала вложенного вызова.

Обозначим S(n) — строку вывода полного вызова F(n), а ε — пустую строку. Результаты вложенных вызовов соединяются в порядке команд. Ниже отдельно записан результат каждого встречающегося аргумента; знак ⧺ означает соединение строк, а не сложение чисел. Это позволяет раскрыть рекурсию от самых коротких вызовов к исходному.

S(1) = ε.
S(2) = ε.
S(3) = «3» ⧺ S(2) ⧺ S(1) = «3».
S(4) = «4» ⧺ S(3) ⧺ S(2) = «43».
S(5) = «5» ⧺ S(4) ⧺ S(2) = «543».
S(6) = «6» ⧺ S(5) ⧺ S(3) = «65433».
S(7) = «7» ⧺ S(6) ⧺ S(3) = «7654333».

Порядок фактической печати при обходе вызовов:
7 → 6 → 5 → 4 → 3 → 3 → 3.
Убираем разделители и получаем 7654333.

Проверка. Отдельное исполнение команд с явным стеком вызовов дало тот же порядок печати 7654333. В трассировке учтены все 15 вызовов и 7 операций печати; после каждого завершения выполнение возвращается к следующей команде, а после ложного условия пропускается только его тело.

Ответ: 7654333.