Рекурсия
Рекурсия – это метод программирования, при котором процедура или функция непосредственно или через другие процедуры (или функции) обращается сама к себе как ко вложенной процедуре (или функции). Это бывает необходимо или удобно для решения целого ряда задач. При использовании рекурсии текст программы и ее алгоритм сокращается и упрощается в несколько раз. Рекурсию следует использовать с осторожностью, так как иногда слишком много рекурсивных вызовов быстро исчерпывают свободную память.
Примеры решения задачи с использованием рекурсии:
Задача 1
Имеется
n
населенных пунктов, перенумерованных
от 1 до n
(n=10).
Некоторые пары пунктов соединены
дорогами. Определить с применением
рекурсии, можно ли попасть по этим
дорогам из 1-го пункта в n-й.
Информация о дорогах задается в виде
пар чисел i
и j
(i
uses
crt;
const
nn=10;
var
rout,r:string;
a:array[0..nn,0..nn]
of char;
i,j,n:integer;
c:char;
ok:boolean;
procedure
router(otkuda,gde ,kuda:integer;var ok:boolean); {рекурсивная
про-}
var
i:integer; {цедура
}
begin
a[gde,otkuda]:='?';
{ ставится на время выполнения процедуры
для }
a[otkuda,gde]:='?';
{исключения зацикливания процедуры}
if
gde=kuda then begin str(kuda,r); ok:=true end
else
for
i:=1
to
nn
do
{ цикл проверки пути по всем направлениям}
begin
if
(ok=false)and(a[i,gde]='y')
then
begin router(gde,i,kuda,ok);{ рекурсивный
вызов
процедуры}
if
ok=true then
begin
str(gde,r); end
end
end;
a[gde,otkuda]:='y';
{ y
- в данном направлении есть дорога}
a[otkuda,gde]:='y';
end;
begin
{начало
программы}
clrscr;
writeln('Введите
пути
');
repeat
write('Откуда
'); readln(i);
if
i<>0 then begin
write(Куда
'); readln(j); writeln(i,' =>',j);
if
j<>0 then
if
(i>nn)or(j>nn) then writeln(‘Неверный
ввод
')
else
begin
a[i,j]:='y';a[j,i]:='y'end else;
end
until
(i=0)or(j=0);
repeat
ok:=true;
repeat
write('Куда
попасть из №1
? ');
rout:='';
readln(n);
if
n<=0 then writeln('Нет
такого!
')
else
if n=1 then writeln('Уже
здесь!
')
else
ok:=false;
until
ok=false;
router(0,1,n,ok);
{результат:
ok=false – дороги
нет,
ok=true – дорога
есть
}
if
ok=false then writeln('Нельзя
')
else
writeln('Можно
');
c:=readkey;
until
c=' ';
end.
Введите
пути
Откуда
1
Куда
2
1
=>2
Откуда
1
Куда
4
1
=>4
Откуда
2
Куда
3
2
=>3
Откуда
4
Куда
6
4
=>6
Откуда
4
Куда
5
4
=>5
Откуда
6
Куда
10
6
=>10
Откуда
00
Куда
попасть из #1 ? 10
Можно
Задача
2
Описать
рекурсивную функцию pow(x,n)
от вещественного x
(x
1 ,
при
n=0;
x
uses
crt;
var
n:integer;
x:real;
function
pow(x:real; n:integer): real; {рекурсивная
функция}
begin
if
n=0 then pow:=1 else
if
n<0>
pow:=x*pow(x,n-1);
{рекурсивный
вызов
pow}
end;
begin
{начало
программы}
clrscr;
write('Введите
x: ');read(x);
write('Введите
n: ');read(n);
writeln('pow
= ',pow(x,n):2:3);
readkey;
end.
x:
2
n:
0
pow
= 1.000
x:
2
n:
3
pow
= 8.000
x:
2
n:
-3
pow
= 0.125
Перечислимые
типы
Перечислимый
тип – это тип составленный из множества
упорядоченных элементов. Перечислимый
тип задается перечислением всех своих
элементов, то есть перечисляются все
возможные значения переменных этого
типа. Над переменными перечислимого
типа можно выполнять только операции
отношения, поскольку значения перечислимого
типа упорядочены, то есть каждому
значению ставится в соответствие его
порядковый номер.
Задача
Type
страна =(Германия, Куба, Лаос, Монако,
Непал, Польша); континент =(Азия, Америка,
Европа). По s
– названию страны определить c
– название континента.
uses
crt;
type
kontinent=(Azia,Amerika,Evropa); {перечислимые
типы}
strana=(Germania,Kyba,Laos,Monako,Nepal,Polsha);
var
c:kontinent;
s:strana;
x:string;
begin
{начало
программы}
clrscr;
write(‘Введите
название страны: ',x);readln(x);
if
x='Германия'
then s:=Germania;
if
x='Куба '
then s:=Kyba;
if
x='Лаос'
then s:=Laos;
if
x='Монако'
then s:=Monako;
if
x='Непал'
then s:=Nepal;
if
x='Польша'
then s:=Polsha;
case
s
of
{выбор континента
по стране}
Laos,Nepal:
c:=Azia;
Kyba:
c:=Amerika;
Germania,Monako,Polsha:
c:=Evropa;
end;
if
c=Azia then writeln('Континент:
Азия');
{вывод
на
экран}
if
c=Amerika then writeln('Континент:
Америка ');
if
c=Evropa then writeln('Континент:
Европа ');
readln;
end.
введите
название страны: Куба
Континент:
Америка
введите
название страны: Германия
Континент:
Европа
введите
название страны: Лаос
Континент:
Азия
Динамические
переменные
Динамические
переменные – это переменные, которые
могут создаваться и уничтожаться в
процессе работы программы. Динамические
переменные применяются тогда, когда
заранее не известно какой объем переменных
потребуется в программе, либо для
организации таких структур данных как
списки или деревья.
Задача
(*
Работа с динамическими переменными
- организация списков *)
USES
CRT;
Type
Str = string[80];
Adr
= ^Zap;
Zap
= Record
Inf
: Integer;
Ssylka
: Adr
End;
procedure
sort(Var Nach:adr);
(*
=============Сортировка
списка ===============*)
Var
i,n:integer;Q:Boolean; P,X:Adr;
Begin
n:=0; Q:=false;
If
Nach=Nil
then
writeln('Список
отсутствует, введите список ')
else
Begin P:=Nach; while P<>Nil do Begin n:=n+1; P:=P^.Ssylka end;
while
not Q do begin Q:=true;P:=Nach;
if
Nach^.inf > Nach^.Ssylka^.inf
then
begin Nach:=Nach^.Ssylka;
P^.Ssylka:=Nach^.Ssylka;
Nach^.Ssylka:=P; Q:=false;
end;
x:=Nach^.Ssylka;P:=Nach;
for
i:=1 to (n-2) do
if
x^.inf > x^.Ssylka^.inf then begin
p^.Ssylka:=
x^.Ssylka; x^.Ssylka:=x^.Ssylka^.Ssylka;
P^.Ssylka^.Ssylka:=x;
P:=P^.Ssylka; Q:=false
end
else
begin P:=x;x:=x^.Ssylka end;
end;
end;
end;
Procedure
Print (P:Adr);
(*
====================Вывод
списка на экран ===============
*)
Var
R:Adr;
Begin
Writeln;
Writeln('______________Печать
списка _________');
R:=P;
Writeln;
While
R<>Nil Do
Begin
Write(R^.Inf,' ');
R:=R^.Ssylka
End;
Writeln;Writeln;Writeln('Список
окончен')
End;
Procedure
sch(Nach:adr);
(*
====================Подсчет
числа элементов списка ========*)
var
r:adr;
i:integer;
begin
i:=0; r:=nach;
while
r<>nil do
begin
i:=i+1;
r:=r^.ssylka
end;
writeln('Количество
элементов’,i);
end;
procedure
DobKon(Var Nach:Adr);
(*
====== Создание списка путем добавления
элементов в конец ====== *)
Var
R,Q:Adr;A:integer;
Begin
Nach:=Nil;
Repeat
write('Введите
число, признак конца
999 ');readln(A);
if
A <> 999 then Begin
if
Nach=Nil
then
Begin New(Nach);Nach^.inf:=A;Nach^.Ssylka:=Nil;Q:=Nach;end
else
Begin New(Q^.Ssylka);Q:=Q^.Ssylka;Q^.inf:=A;Q^.Ssylka:=NIL;
end
end
Until
A=999;
end;
procedure
DobNach(Var Nach:Adr);
(*
====== Создание списка путем добавления
элементов в начало ==== *)
Var
R : Adr;
A
: Integer;
begin
nach:=nil;
repeat
write
('Введите число, признак конца
999 ');
readln(a);
if
a<>999 then begin
new(r);
r^.inf:=a;
r^.ssylka:=nach;
nach:=R;end
Until
a=999
end;
var
R: integer;
Function
Poisk(Nach:Adr;R:Integer):Adr;
(*
===== Поиск элемента R
в списке (рекурсивный)===================*)
(*
результат - адрес этого элемента
Nil,
если элемент не найден *)
Begin
If Nach=Nil Then Poisk:=Nil
Else
If Nach^.Inf=R Then Poisk:=Nach
Else
Poisk:=Poisk(Nach^.Ssylka,R);
end;
Procedure
VstavZ(Nach:Adr);
(*===Вставка
в список элемента после элемента с
заданным значением ===*)
Var
AZ,AVst,R:Adr;{Адрес
заданного элемента и адрес вставленного,
рабочий адрес}
Z
:Integer;
Begin
Write('Введите
элемент, после которого хотите произвести
вставку ');
Readln(Z);
R:=Nach;
While
(R^.Ssylka<>Nil) And (R^.Inf<>Z) do
{пока
не закончится список или не найдется
нужный элемент}
R:=R^.Ssylka;
{продвигаемся по списку}
If
R^.Inf<>Z
Then
Writeln('Заданного
элемента нет')
Else
Begin New(Avst);
Avst^.Ssylka:=R^.Ssylka;
Write('Что
хотите вставить? ');
Readln(Avst^.Inf);
R^.Ssylka:=Avst
End
End;
Procedure
IsklN(Var Nach:Adr);
(*=======Исключение
из списка элемента с заданным номером
=======*)
Var
N,
I
: Integer;
{Номер исключаемого элемента, текущий
номер}
R
: Adr;
{Текущий адрес}
Begin
Write('Введите
номер удаляемого элемента '); Readln(N);
If
N=1 Then Nach:=Nach^.Ssylka
Else
Begin R:=Nach; I:=1;
While
(R^.SSylka<>Nil)
And
(I
Begin
R:=R^.Ssylka; I:=I+1 End;
If
R^.ssylka=Nil
Then
Writeln('Элемента
с таким номером нет’)
Else
R^.Ssylka:=R^.Ssylka^.Ssylka
End
End;
Procedure
PrintF(Var Nach:Adr;Var S:str);
(*
===== Запись списка в файл на диск ======= *)
Var
F:Text;R:Adr;
Begin
Write('Имя
файла?
');readln(s);
Assign(F,s);
rewrite(F);
If
Nach<>nil then Begin writeln(F,'---- Список
элементов
----');
writeln(F);
R:=Nach;
While
r<>Nil do
Begin
write(F,R^.inf:6);
R:=R^.Ssylka
end;
writeln(F);writeln(f);
Writeln(F,'-----
Список
окончен
-----'); close(F);
Writeln('Запись
списка в файл ',s,'
произведена');
end
else
writeln('Список
отсутствует, введите список');
end;
function
Kolich(Var Nach:Adr;r:integer):integer;
(*
===== Сколько раз встречается заданный
элемент ======= *)
var
P:adr;
i:integer;
begin
i:=0; P:=nach;
while
P<>nil do
begin
if
P^.inf=r then i:=i+1;
P:=P^.ssylka
end;
Kolich:=i;
END;
procedure
Skleika(var Nach:adr;var Nach1:adr);
var
r:adr;
begin
r:=nach;
while
r^.ssylka<>nil do r:=r^.ssylka;
r^.ssylka:=nach1;
end;
{-------------------------------------------------------------------}
Var
F : Text;
x,y,t,Xx
: Integer;
s,key
: Char;
s1
: Str;
Var
Nach,Nach1,q,PPP : Adr;
Const
K=12;{Количество
вариантов в "меню"}
Begin
Nach:=Nil;
Repeat
x:=3;
y:=1;
ClrScr;
Writeln
(' 0. Конец
работы');
Writeln
(' 1. Печать
списка
');
Writeln
(' 2. Создание
списка путем добавления элементов в
начало');
Writeln
(' 3. Есть
ли в списке заданный элемент');
Writeln
(' 4. Вставка
элемента после заданного');
Writeln
(' 5. Удаление
элемента с заданным номером');
Writeln
(' 6. Сколько
раз встречается заданный элемент’);
Writeln
(' 7. Подсчитать
количество элементов списка’);
Writeln
(' 8. Склеить
два списка');
Writeln
(' 9. Создание
списка путем добавления элемента в
конец ');
Writeln
(' 10. Запись
списка в файл на диск ');
Writeln
(' 11. Сортировка
списка');
Repeat
Gotoxy(X,Y);
s:=readkey;
if s=#0 then s:=readkey;
t:=ord(s);
Case
t of
72:if
y>1 then y:=y-1 else y:=k;
80:if
y
End;
Until
t=13;
ClrScr;
Case
Y-1 of
1:Begin
writeln('Использовать
Print(Nach)');
Print(Nach);
end;
2:
Begin writeln('Использовать
DobNach(Nach);Print(Nach)');
DobNach(Nach);
Print(Nach);
end;
3:
Begin writeln(' Использовать
Print(Nach),Poisk(Nach,R)');
repeat;
Print(Nach);
write('Введите
элемент, который надо найти :');
readln(R);
ppp:=Poisk(Nach,R);
if
ppp<>nil then writeln('Элемент
найден
',ppp^.inf)
else
writeln('Элемент
не найден');
Print(Nach);
writeln;writeln('Повторить?');
until
readkey='n';
end;
4:
Begin writeln(' Использовать
Print(Nach),VstavZ(Nach)');
repeat
Print(Nach);
VstavZ(Nach);
Print(Nach);
writeln;writeln('Повторить?');
until
readkey='n';
end;
5:
Begin writeln(' Использовать
Print(Nach),IsklN(Nach)');
repeat
Print(Nach);
IsklN(Nach);
Print(Nach);
writeln;writeln('Повторить?');
until
readkey='n';
end;
6:
Begin writeln('Создать
свою
процедуру
Kolich(Nach)');
Print(Nach);
write('Введите
элемент, который надо найти: ');
readln(R);
writeln('Элемент
в списке встречается ',Kolich(Nach,r),'
раз(а)');
end;
7:
Begin writeln('Использовать
print(Nach) и
sch(Nach)');
print(Nach);
sch(Nach);
end;
8:
Begin writeln('Создать
свою
процедуру
Skleika(Nach,Nach1)');
writeln('Введите
второй список ');
dobkon(nach1);
print(nach);
print(nach1);
Skleika(Nach,Nach1);
print(nach);
end;
9:
Begin
writeln('Использовать
DobKon(Nach);Print(Nach)');
DobKon(Nach);
Print(Nach);
end;
10:
Begin
writeln('Использовать
PrintF(Nach,S1)');
PrintF(Nach,S1);
end;
11:
Begin
writeln('
Использовать
sort(Nach); Print(Nach)');
print(Nach);
sort(Nach);
print(Nach);
end;
End;
writeln;writeln('Нажми
любую
клавишу,
кроме
Enter');
repeat
key:=readkey until key<>#13;
Until
Y=1;
End.
Создание
списка путем добавления элемента в
конец.
Использовать
DobKon(Nach);Print(Nach)
Введите
число,признак конца 999 1
Введите
число,признак конца 999 4
Введите
число,признак конца 999 6
Введите
число,признак конца 999 2
Введите
число,признак конца 999 8
Введите
число,признак конца 999 11
Введите
число,признак конца 999 2
Введите
число,признак конца 999 5
Введите
число,признак конца 999 999
______________Печать
списка_________
1
4 6 2 8 11 2 5
Список
окончен
Сколько
раз встречается заданный элемент
Создать
свою процедуру Kolich(Nach)
______________Печать
списка_________
1
4 6 2 8 11 2 5
Список
окончен
Введите
элемент, который надо найти :2
Элемент
в списке встречается 2 раз(а)
Есть
ли в списке заданный элемент.
Использовать
Print(Nach),Poisk(Nach,R)
______________Печать
списка_________
1
4 6 2 8 11 2 5
Список
окончен
Введите
элемент, который надо найти :6
Элемент
найден 6
Введите
элемент, который надо найти :10
Элемент
не найден
Склеить
два списка.
Создть
свою процедуру Skleika(Nach,Nach1)
Введите
второй список
Введите
число,признак конца 999 1
Введите
число,признак конца 999 2
Введите
число,признак конца 999 3
Введите
число,признак конца 999 999
______________Печать
списка_________
1
2 5 6 3
Список
окончен
______________Печать
списка_________
1
2 3
Список
окончен
______________Печать
списка_________
1
2 5 6 3 1 2 3
Список
окончен
0)
и целого n,
которая вычисляет величину
согласно формуле:= 1/ ,
при
n<0>
,
при
n>0
