Лекция 1 Программирование с использованием рекурсивных процедур и функций

Лекция 1

Программирование с использованием рекурсивных процедур и функций

Рекурсия (от латинского recursio – возвращение) — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Вообще, рекурсивным называется любой объект, который частично определяется через себя.

Пример 1. Что будет делать следующая программа?

Program A;

Procedure Privet;

Begin

Writeln(‘Привет’);

Privet

End;

Begin

Privet

End.

Ответ: процедура будет бесконечно выводить на экран слово “Привет”.

В действительности, такой бесконечный вызов приводит к переполнению памяти и возникновению ошибки.

Вообще, в рекурсивном определении должно присутствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.

Примеры рекурсивных определений:

1. Определение факториала. С одной стороны, факториал определяется так: n!=1*2*3*...*n. С другой стороны, Граничным условием в данном случае является n<=1.

2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n:

Задание. По аналогии определите функцию S(n), вычисляющую сумму цифр заданного натурального числа.

Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При каждом рекурсивном вызове информация о нем сохраняется в специальной области памяти, называемой стеком. В стеке записываются значения локальных переменных, параметров подпрограммы и адрес точки возврата. Таким образом, какой-либо локальной переменной A на разных уровнях рекурсии будут соответствовать разные ячейки памяти, которые могут иметь разные значения. Поэтому воспользоваться значением переменной A i‑ого уровня можно только находясь на этом уровне. Информация в стеке для каждого вызова подпрограммы будет порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост количества информации в стеке приведёт к аварийному завершению программы за счёт переполнения стека.

Выполнение действий в рекурсивной подпрограмме может быть организовано одним из вариантов. Порождение все новых вызовов рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество вызовов рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным возвратом.

1) Выполнение действий на рекурсивном спуске.

Procedure Rec;

Begin

<действия на входе в рекурсию>;

If <проверка условия> then Rec

[else S]

end;

Обычно проверяют, что с каждым рекурсивным вызовом значение какого-то параметра уменьшается, и это не может продолжаться бесконечно.

Program factor1;

Var f, n:integer;

Procedure fact(k:integer; var S:integer);

Begin

If k>=1 then

Begin

S:=k*S;

Fact(k-1,S)

End;

End;

Begin

Readln(n);

F:=1;

Fact(n, f);

Writeln(f)

End.

Уровень	Спуск	Возврат
	K	S	Fact
0	4	1	Fact(4,1)	24
1	4	4	Fact(3,4)	24
2	3	12	Fact(2,12)	24
3	2	24	Fact(1,24)	24
4	1	24	Fact(0,24)	24
5	0

2) Выполнение действий на рекурсивном возврате.

Procedure Rec;

Begin

If <проверка условия> then Rec

[else S1];

<действия на выходе из рекурсии>;

end;

Program factor2;

Var f, n:integer;

Function fact(k:integer):integer;

Begin

If k>=1 then fact:=fact(k-1)*k

Else fact:=1

End;

Begin

Readln(n);

Writeln(fact(n))

End.

Уровень	Спуск	Возврат
	K	Fact
0	4	Fact(4)	24
1	4	Fact(3)*4	24
2	3	Fact(2)*3	12
3	2	Fact(1)*2	4
4	1	Fact(0)*2	2
5	0	1

3) Выполнение действий на рекурсивном спуске и на рекурсивном возврате.

Procedure Rec;

Begin

<действия на входе в рекурсию>;

If условие then Rec;

<действия на выходе из рекурсии>

end;

или

Procedure Rec;

Begin

If условие then

begin

<действия на входе в рекурсию>;

Rec;

<действия на выходе из рекурсии>

End;

end;

Program factor3;

Var f, n:integer;

Function fact(k:integer):integer;

Begin

f:=f*k;

If k>1 then

Fact:=Fact(k-1)

Else

Fact:=f;

End;

Begin

Readln(n);

f:=1;

Writeln(fact(n))

End.

При n=4:

Уровень	Спуск	Возврат
	K	F	fact	Fact
0	4	1	Fact(4)	24
1	4	4	Fact(3)	24
2	3	12	Fact(2)	24
3	2	24	Fact(1)	24
4	1	24

Задание 1. Написать рекурсивную программу нахождения количества цифр целого натурального числа n.

1) Выполнение действий на рекурсивном спуске:

procedure K(N:longint; var kol:byte);

begin

if N<10

then Kol:=Kol+1

else begin

Kol:=Kol+1;

K(N div 10, Kol);

End;

end;

2) Выполнение действий на рекурсивном возврате:

procedure K(N:longint; var kol:byte);

begin

if N<10

then Kol:=1

else begin

K(N div 10, Kol);

Kol:=Kol+1;

End;

end;

или

Function K(N:Longint):Byte;

Begin

If N<10

Then K:=1

Else K:=K(N div 10)+1

End;

3) Выполнение действий на рекурсивном спуске и на рекурсивном возврате:

program p1;

var n1:Longint; kol:Byte;

Function K(N:Longint):Byte;

Begin

kol:=kol+1;

If N<10

Then K:=kol

Else K:=K(N div 10);

End;

begin

readln(n1);

kol:=0;

writeln('kol=',k(n1));

end.

Задание 2. Вычислить сумму элементов одномерного массива.

При решении задачи используем следующее соображение: сумма равна нулю, если количество элементов равно нулю, и сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю.

Program Rec;

Type Mas = Array[1..100] Of Integer;

Var A:Mas; I, N:Byte;

{Рекурсивная функция}

Function Summa(N : Byte; A: Mas) : Integer;

Begin

If N = 0

Then Summa := 0

Else Summa := A[N] + Summa(N - 1, A)

End;

{Основная программа}

Begin

Write('Количество элементов массива? ');

ReadLn(N);

Randomize;

For I := 1 To N Do

Begin

A[I] := -10 + Random(21);

Write(A[I] : 4)

End;

WriteLn; WriteLn('Сумма: ', Summa(N, A))

End.

Задание 3. Определить, является ли заданная строка палиндромом, т. е. читается одинаково слева направо и справа налево.

Идея решения заключается в просмотре строки одновременно слева направо и справа налево и сравнении соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом. Граничное условие — строка является палиндромом, если она пустая или состоит из одного символа.

Program Palindrom;

{Рекурсивная функция}

Function Pal(S: String) : Boolean;

Begin

If Length(S)<=1

Then Pal:=True

Else Pal:= (S[1]=S[Length(S)]) and Pal(Copy(S, 2, Length(S;

End;

Var S : String;

{Основная программа}

Begin

Write('Введите строку: '); ReadLn(S);

If Pal(S)

Then WriteLn('Строка является палиндромом')

Else WriteLn('Строка не является палиндромом')

End.

Рассмотренные выше программы использовали так называемую прямую рекурсию, когда в теле некоторой процедуры содержался непосредственный вызов самой себя.

В языке Паскаль допускается также и косвенная рекурсия, когда, например, процедура, процедура А вызывает процедуру В, а та, в свою очередь,- процедуру А. Длина таких цепочек вызовов может быть произвольной, однако при разработке программы необходимо тщательно следить за тем, чтобы рекурсивный алгоритм был сходимым, то есть не приводил к бесконечным взаимным вызовам подпрограмм.

Пример

Программа иллюстрирует косвенные рекурсивные вызовы процедур. В этой программе процедуры Rec1 и Rec2 рекурсивно вызывают друг друга, поочередно уменьшая свои фактические параметры. Обе процедуры работают с одной глобальной переменной А, которая передается в них по ссылке. Критерием завершения работы является обращение этой переменной в ноль.

В программе необходимо предварительное определение второй процедуры Rec2, так как ее вызов встречается в процедуре Rec1, т. е. перед ее полным описанием.

Program KosvRecurs;

Var A : integer;

Procedure Rec2 (Var Y:integer); Forward[1];

Procedure Rec1 (Var X:integer);

Begin

X := X-1;

if X>0 then

Begin

writeln (‘X=’,X);

Rec2(X)

End

End;

Procedure Rec2 (Var Y:integer);

Begin

Y := Y div 2;

if Y>2 then

Begin

writeln (‘Y=’,Y);

Rec1(Y)

End

End;

Begin

A := 15;

Rec1(A);

writeln (‘A=’,A)

End.

Что будет напечатано на экране?

Ответ:

X=14

Y=7

X=6

Y=3

X=2

A=1

Использование рекурсии является красивым приёмом программирования. Рекурсивные версии программ, как правило, гораздо короче и нагляднее. В то же время в большинстве практических задач этот приём неэффективен с точки зрения расходования таких ресурсов ЭВМ, как память и время исполнения программы. Использование рекурсии увеличивает время исполнения программы и зачастую требует значительного объёма памяти для хранения копий подпрограммы на рекурсивном спуске. Поэтому на практике разумно заменять рекурсивные алгоритмы на итеративные. А любой рекурсивный алгоритм можно преобразовать в эквивалентный итеративный (то есть использующий циклические конструкции).

[1] Опережающее объявление

В некоторых ситуациях возникает необходимость вызвать подпрограмму, описанную далее по тексту программы. Например, эта необходимость возникает при косвенной рекурсии (подпрограмма A вызывает подпрограмму B, а та в свою очередь вызывает подпрограмму A). В этом случае используется опережающее объявление подпрограммы, состоящее из ее заголовка, за которым следует служебное слово forward.

Например:

procedure B(i: integer); forward;

Запрещено делать опережающее объявление для уже описанной подпрограммы.