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

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

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

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

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

S(0) = «0» = «0».
S(1) = «1» = «1».
S(2) = «2» ⧺ S(0) ⧺ S(1) ⧺ S(0) = «2010».
S(3) = «3» ⧺ S(1) ⧺ S(2) ⧺ S(1) = «3120101».

Порядок фактической печати при обходе вызовов:
3 → 1 → 2 → 0 → 1 → 0 → 1.
Убираем разделители и получаем 3120101.

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

Ответ: 3120101.