Основы алгоритмизации и программирования. Часть третья. Структурированные типы данных. Асламова В.С - 16 стр.

UptoLike

ВУЗ: 

АГТА | Ангарск

Составители: 

Рубрика: 

31
передавать их в качестве параметров при вызове компилятора командной
строкой.
Типичная конструкция рекурсии
procedure proc(i:integer);
begin
оператор 1
if условие then proc(i+1);
оператор 2
end;
Вызов proc(1) означает, что процедура proc вызывает себя раз за
разом с помощью proc(2), proc(3), . . . до тех пор, пока условие имеет
значение true. Как только значение условия false (не выполняется), то
отменяется вызов proc(i+1), чтобы для каждого вызова был отработан
оператор 2 (группа операторов). Все локальные переменные процедуры
сохраняются в стеке. Если,
например, при proc(10) условие ложно, то
оператор 2 выполняется со значениями, которые выбираются из стека в
обратном порядке, т.е. вначале для proc(10), proc(9), ……., proc(1).
В Паскале можно пользоваться именами лишь тогда, когда в тексте
программы этому предшествует их описание. Рекурсия является
единственным исключением из этого случая. Имя proc можно использовать
сразу же, не окончив его описания
.
Рекурсию нельзя воспринимать как некий трюк, скорее это метод.
Если что-нибудь нужно выполнить повторно, то можно действовать двумя
способами:
1. С помощью последовательного присоединения (или итерация в
форме цикла);
2. С помощью вложения одной операции в другую – рекурсия..
Пример 9:
Этот пример показывает принципиальное различие между итерацией
и рекурсией. Итерации необходим цикл и локальная переменная k как
параметр цикла. В этом примере один раз счет ведётся от 1 до n с помощью
цикла, а второй - с помощью рекурсии. При этом видно как заполняется, а
затем освобождается стек.
32
В процедуре recursion операция writeln(i:30) выполняется перед
рекурсивным вызовом, после того как i<1 начинает освобождаться стек с
помощью writeln(i:3). Поскольку рекурсия выполняется от n до 1, то вывод
по команде writeln(i:30) выполняется в обратной последовательности n,n-
1,…,1, а вывод по команде writeln(i:3) в прямой последовательности 1,2,…..,n
(согласно принципу LIFO – последним пришел, первым обслужен).
program iterativ_recursion;
var n:integer;
procedure recursion(i:integer); {рекурсия}
begin
writeln(i:30);
if i>1 then recursion (i-1);
writeln(i:3);
end;
procedure cike(i:integer); {цикл
}
var k:integer:
begin
for k:=1 to i do write(k:3);
end;
begin {начало выполняемой части программы}
writeln(′ввод n′);
readln(n);
write(′в цикле: ′);
cike(n); writeln;
writeln(′при рекурсии : ′);
recursion(n);
end.
Пример 10:
Рекурсивная процедура convert переводит десятичное число z в
восьмеричную систему путём деления его на 8 и выдачи остатка в обратной
последовательности.
program dezimal_oktal_konvertierung;
var z:integer;
procedure convert(z:integer); {преобразование десятичной системы в
восьмеричную}
begin
if z>1 then convert (z div8);
write (z mod 8:1);
end; 
передавать их в качестве параметров при вызове компилятора командной               В процедуре recursion операция writeln(i:30) выполняется перед
строкой.                                                                   рекурсивным вызовом, после того как i<1 начинает освобождаться стек с
                                                                           помощью writeln(i:3). Поскольку рекурсия выполняется от n до 1, то вывод
                    Типичная конструкция рекурсии                          по команде writeln(i:30) выполняется в обратной последовательности n,n-
                                                                           1, ,1, а вывод по команде writeln(i:3) в прямой последовательности 1,2, ..,n
                                                                           (согласно принципу LIFO – последним пришел, первым обслужен).
   procedure proc(i:integer);
   begin
           оператор 1                                                         program iterativ_recursion;
         if условие then proc(i+1);                                           var n:integer;
           оператор 2                                                         procedure recursion(i:integer);              {рекурсия}
   end;                                                                       begin
                                                                                  writeln(i:30);
      Вызов proc(1) означает, что процедура proc вызывает себя раз за             if i>1 then recursion (i-1);
разом с помощью proc(2), proc(3), . . . до тех пор, пока условие имеет            writeln(i:3);
значение true. Как только значение условия false (не выполняется), то         end;
отменяется вызов proc(i+1), чтобы для каждого вызова был отработан            procedure cike(i:integer);                   {цикл}
оператор 2 (группа операторов). Все локальные переменные процедуры            var k:integer:
                                                                              begin
сохраняются в стеке. Если, например, при proc(10) условие ложно, то               for k:=1 to i do write(k:3);
оператор 2 выполняется со значениями, которые выбираются из стека в           end;
обратном порядке, т.е. вначале для proc(10), proc(9), ., proc(1).             begin                            {начало выполняемой части программы}
      В Паскале можно пользоваться именами лишь тогда, когда в тексте             writeln(′ввод n′);
программы этому предшествует их описание. Рекурсия является                       readln(n);
                                                                                  write(′в цикле: ′);
единственным исключением из этого случая. Имя proc можно использовать
                                                                                  cike(n); writeln;
сразу же, не окончив его описания.                                                writeln(′при рекурсии : ′);
       Рекурсию нельзя воспринимать как некий трюк, скорее это метод.             recursion(n);
Если что-нибудь нужно выполнить повторно, то можно действовать двумя          end.
способами:
      1. С помощью последовательного присоединения (или итерация в                 Пример 10:
форме цикла);                                                                     Рекурсивная процедура convert переводит десятичное число z в
      2. С помощью вложения одной операции в другую – рекурсия..           восьмеричную систему путём деления его на 8 и выдачи остатка в обратной
        Пример 9:                                                          последовательности.
                                                                              program dezimal_oktal_konvertierung;
        Этот пример показывает принципиальное различие между итерацией        var z:integer;
и рекурсией. Итерации необходим цикл и локальная переменная k как             procedure convert(z:integer);     {преобразование десятичной системы в
параметр цикла. В этом примере один раз счет ведётся от 1 до n с помощью                                                              восьмеричную}
цикла, а второй - с помощью рекурсии. При этом видно как заполняется, а       begin
затем освобождается стек.                                                        if z>1 then convert (z div8);
                                                                                 write (z mod 8:1);
                                                                              end;
                                      31                                                                        32

Страницы