Имитация работы цикла с помощью рекурсии
Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия - основной прием программирования).
Для примера сымитируем работу цикла for. Для этого нам потребуется переменная счетчик шагов, которую можно реализовать, например, как параметр процедуры.
Пример 1.
procedure LoopImitation(i, n: integer); {Первый параметр – счетчик шагов, второй параметр – общее количество шагов} begin writeln('Hello N ', i); //Здесь любые инструкции, которые будут повторятся if i<n then //Пока счетчик цикла не станет равным максимальному LoopImitation(i+1, n); //значению n, повторяем инструкции путем вызова //нового экземпляра процедуры end; |
Результатом вызова вида LoopImitation(1, 10) станет десятикратное выполнение инструкций с изменением счетчика от 1 до 10. В данном случае будет напечатано:
Hello N 1
Hello N 2
…
Hello N 10
Вообще, не трудно видеть, что параметры процедуры это пределы изменения значений счетчика.
Можно поменять местами рекурсивный вызов и подлежащие повторению инструкции, как в следующем примере.
Пример 2.
procedure LoopImitation2(i, n: integer); begin if i<n then LoopImitation2(i+1, n); writeln('Hello N ', i); end; |
В этом случае, прежде чем начнут выполняться инструкции, произойдет рекурсивный вызов процедуры. Новый экземпляр процедуры также, прежде всего, вызовет еще один экземпляр и так далее, пока не дойдем до максимального значения счетчика. Только после этого последняя из вызванных процедур выполнит свои инструкции, затем выполнит свои инструкции предпоследняя и т.д. Результатом вызова LoopImitation2(1, 10) будет печать приветствий в обратном порядке:
Hello N 10
…
Hello N 1
Если представить себе цепочку из рекурсивно вызванных процедур, то в примере 1 мы проходим ее от раньше вызванных процедур к более поздним. В примере 2 наоборот от более поздних к ранним.
Наконец, рекурсивный вызов можно расположить между двумя блоками инструкций. Например:
procedure LoopImitation3(i, n: integer); begin writeln('Hello N ', i); {Здесь может располагаться первый блок инструкций} if i<n then LoopImitation3(i+1, n); writeln('Hello N ', i); {Здесь может располагаться второй блок инструкций} end; |
Здесь сначала последовательно выполнятся инструкции из первого блока затем в обратном порядке инструкции второго блока. При вызове LoopImitation3(1, 10) получим:
Hello N 1
…
Hello N 10
Hello N 10
…
Hello N 1
Потребуется сразу два цикла, чтобы сделать то же самое без рекурсии.
Тем, что выполнение частей одной и той же процедуры разнесено по времени можно воспользоваться. Например:
Дата добавления: 2016-07-05; просмотров: 1982;