5.9 Рекурсия в подпрограммах
В теле подпрограммы доступны все объекты, описанные в основной программе, в том числе и имя самой подпрограммы. Таким образом, внутри тела подпрограммы возможен вызов самой подпрограммы. Процедуры и функции, использующие вызовы «самих себя», называются рекурсивными.
Многие математические алгоритмы имеют рекурсивную природу, поэтому рекурсия широко используется в программировании. В качестве примера приведем известный алгоритм вычисления факториала неотрицательного целого числа:
(0!=1)
1!=1
N!=1*2*3*…*(N-1)*N
алгоритм основан на соотношении N!=(N-1)!*N
Пример:
function fact(N: word): longint;
begin
if (n=0) or (n=1) then fact:=1
else fact:=n*fact(n-1);
end;
При каждом новом обращении к подпрограмме параметры, которые она использует, заносятся в стек, причем параметры предыдущего обращения тоже сохраняются.
Рекурсивное оформление программы более компактно и эффективно, но не следует забывать об опасности переполнения стека (!).
Схема вызовов при вычислении 5!:
fact(5); 1*2*3*4*5
fact(4); 1*2*3*4
fact(3); 1*2*3
fact(2); 1*2
fact(1); 1
Задачи для самоконтроля
5.1 Определите значение переменных a, b после выполнения следующих программ:
|
а) var a,b: integer; procedure proc(x: integer; y: integer); begin y:= y+2; x:= x+2;
~ begin a:=15; b:=15; proc(a,b); writeln(‘a = ’,a,’ b= ‘,b); end.
|
б) var a,b: integer; procedure proc(x: integer; var y: integer); begin y:= y+2; x:= x+2;
~ begin a:=15; b:=15; proc(a,b); writeln(‘a = ’,a,’ b= ‘,b); end. |
|
в) var a,b: integer; procedure proc(var x: integer; y: integer); begin y:= y+2; x:= x+2;
~ begin a:=15; b:=15; proc(a,b); writeln(‘a = ’,a,’ b= ‘,b); end. |
г) var a,b: integer; procedure proc(x: integer; var y: integer); begin y:= y+2; x:= x+2;
~ begin a:=15; b:=15; proc(a,b); writeln(‘a = ’,a,’ b= ‘,b); end. |
6. Строковый тип данных
6.1 Описание строк
Строка – это последовательность символов произвольной длины (до 255 символов). Строку можно рассматривать, как массив символов переменной длины. Максимальное количество символов в строке указывается при ее описании в квадратных скобках:
var str1: string[80];
str2: string;
Если в квадратных скобках не указан максимальный размер строки, то он считается равным 255.
Строка может быть описана как типизированная константа:
const str10: string[10]=’январь’;
В памяти для строки длины N отводится N+1 байт, пронумерованных от 0 до N. В нулевом байте хранится текущее значение длины строки.
0 1 2 3 4 5 6 … 10
|
6 |
я |
н |
в |
а |
р |
ь |
|
|
|
Когда изменяется содержание строки, автоматически пересчитывается ее текущая длина и меняется значение 0-го байта. Всегда можно определить текущую длину строки:
l:=ord(str10[0]);
writeln(l);
Допустимо обращение к отдельным символам строки:
var s: string;
begin
s:=’стол’;
writeln(s); стол
s[3]:=’у’;
writeln(s); стул
end.