Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Имитация работы цикла с помощью рекурсии
|
|
Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия - основной прием программирования).
Для примера сымитируем работу цикла 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
Потребуется сразу два цикла, чтобы сделать то же самое без рекурсии.
Тем, что выполнение частей одной и той же процедуры разнесено по времени можно воспользоваться. Например:
Пример 3: Перевод числа в двоичную систему.
Получение цифр двоичного числа, как известно, происходит с помощью деления с остатком на основание системы счисления 2. Если есть число 
, то его последняя цифра в его двоичном представлении равна
.
Взяв же целую часть от деления на 2:
,
получим число, имеющее то же двоичное представление, но без последней цифры. Таким образом, достаточно повторять приведенные две операции пока поле очередного деления не получим целую часть равную 0. Без рекурсии это будет выглядеть так:
| while x>0 do begin c:=x mod 2; x:=x div 2; write(c); end; |
Проблема здесь в том, что цифры двоичного представления вычисляются в обратном порядке (сначала последние). Чтобы напечатать число в нормальном виде придется запомнить все цифры в элементах массива и выводить в отдельном цикле.
С помощью рекурсии нетрудно добиться вывода в правильном порядке без массива и второго цикла. А именно:
| procedure BinaryRepresentation(x: integer); var c, x: integer; begin {Первый блок. Выполняется в порядке вызова процедур} c:= x mod 2; x:= x div 2; {Рекурсивный вызов} if x>0 then BinaryRepresentation(x); {Второй блок. Выполняется в обратном порядке} write(c); end; |
Вообще говоря, никакого выигрыша мы не получили. Цифры двоичного представления хранятся в локальных переменных, которые свои для каждого работающего экземпляра рекурсивной процедуры. То есть, память сэкономить не удалось. Даже наоборот, тратим лишнюю память на хранение многих локальных переменных x. Тем не менее, такое решение кажется мне красивым.
Date: 2016-07-18; view: 409; Нарушение авторских прав