ГДЗ по информатике 11 класс Босова, номер §9 № 13

§ №

Трассировка рекурсивной процедуры

Дана программа:

program rek;
procedure F(n: integer);
begin
  if n > 0 then
  begin
    F(n - 4);
    writeln(n);
    F(n div 3)
  end;
end;
begin
  F(9)
end.

Не выполняя программу на компьютере, выясните, что получится в результате работы этой программы. Проверьте свой результат, выполнив программу на компьютере.

Решение

По правилу выполнения процедуры сначала проверяется . При тело ветвления пропускается и ничего не выводится. При положительном порядок строго таков: сначала F(n - ), затем writeln(n), потом F(n div ). Поэтому число печатается после полного завершения первого рекурсивного вызова, но до второго.

Проследим вызовы слева направо; «—» означает, что число не печатается:

Вызов	Первый вызов `F(n-)`	Вывод `n`	Последний вызов `F(n div )`
`F()`	`F()`		`F()`
`F()`	`F()`		`F()`
каждый `F()`	`F(-)`		`F()`
`F()`	`F(-)`		`F()`
`F(-)`, `F(-)`, `F()`	—	—	—

Развернём порядок исполнения. Первый F() внутри F() выводит , затем F() выводит , второй F() внутри него выводит . Только после завершения F() исходный вызов выводит . Далее выполняется F(): его первый вызов F(-) ничего не печатает, поэтому выходит ; последний вызов F() выводит . Значит, при запуске программы строки появляются в порядке , , , , , .

Ответ

Программа выводит по отдельным строкам: , , , , , .

Помогло?

Номер §9 № 13