Форум » Циклы, ветвления, рекурсия » Рекурсия » Ответить

Рекурсия

Артем: procedure F(n: integer); begin write(n); if n > 2 then begin F(n − 1); F(n − 2); F(n − 3) end end; Что вы-ве-дет про-грам-ма при вы-зо-ве F(4)? В от-ве-те за-пи-ши-те по-сле-до-ва-тель-ность вы-ве-ден-ных цифр слит-но (без пробелов). Почему в ответе: F(4) { F(3) { F(2) F(1) F(0) } F(2) F(1) } У меня получается 4321210. Почему в ответе как бы "прыгают" на нуль, а потом переходят к двойке, а затем к единице?

Ответов - 3

Поляков: Артем пишет: Почему в ответе как бы "прыгают" на нуль, а потом переходят к двойке, а затем к единице? Тут сложно объяснять на пальцах, легче набрать программу и пройти в пошаговом режиме. Общая идея такова: сначала выполняется первый вызов до конца, то есть до того момента, пока не будет ложно условие n > 2. Вызываются последовательно F(4-1) -> F(2) (выводит 32) и на этом рекурсивные вызовы в первой ветке заканчиваются. Затем отрабатывается ветка F(3) -> F(1), она выводит 1, затем ветка F(4-1)->F(0) выводит 0. Дальше аналогично ветка F(4-2) выводит 2 и F(4-3) выводит 1. Последние два вызова не приводят к продолжению рекурсии.

Victor1010: Можно прокрутить все, что происходит, но пока оставить функции с аргументами, а потом потихоньку раскрывать f(4) = 4 f(3) f(2) f(1) f(4) = 4 3 f(2) f(1) f(0) f(2) f(1) f(4) = 4 3 2 1 0 2 1

Поляков: Victor1010 пишет: Можно прокрутить все, что происходит, но пока оставить функции с аргументами, а потом потихоньку раскрывать Действительно, неплохой способ объяснения.



полная версия страницы