Рекурсия. Нетипизированные параметры

End.

Begin

Описание функций

Нетипизированные параметры

Как можно догадаться из названия, при описании нетипизированных параметров не указывается тип. Передаются они всегда по адресу - либо как константы, либо как переменные, например:

procedure P(const a, b; var y); Есть одно важное ограничение: передать-то их можно, а вот делать с ними в подпрограмме что-либо до тех пор, пока они не приведены к какому-то определенному типу, все равно нельзя! Пример. Функция сравнения на равенство двух величин произвольного размера и типа.Function EQ(const x, y; size: word): boolean;type mas_byte = array[0.. MaxInt] of byte;var n: integer;begin n:= 0; while (n < size) and (mas_byte(x)[n] = mas_byte(y)[n]) do inc(n); EQ:= n = size;end;

В эту функцию фактически передаются только адреса начала расположения в памяти двух переменных, поэтому необходим еще один параметр: длина сравниваемых величин в байтах (параметр size). Единственный способ выяснить, равны ли две величины, размер которых заранее не известен - их побайтное сравнение, поэтому оба параметра приводятся к типу mas_byte, объявленному в функции. При описании массива используется стандартная константа MaxInt, в которой хранится максимальное значение для величин типа integer, то есть 32767.

С помощью функции EQ можно сравнить две любые величины.

Описание функции имеет следующую структуру:

function имя (список формальных параметров): тип результата;

label

const Описание локальных меток,

type констант, типов и переменных

var

procedure Описание внутренних процедур

function и функций

Операторы, среди которых хотя бы один, который присваивает имени функции значение результата

Типом результата в функциях может быть любой из стандартных типов Паскаля, кроме файловых типов. Использование конструируемых типов здесь недопустимо.

Параметры функции являются ее аргументами.

Задача 3. Вычислить площадь треугольника, зная его стороны и диагональ.

program pl;var AB, BC, CD, DA,AC, s1, s2, s: real;function st(a, b, c: real): real;var p: real;begin p:=(a+b+c)/2; st:=sqrt(p*(p-a)*(p-b)*(p-c))end;begin write('Введите стороны и диагональ:'); readln(AB, BC, CD, DA,AC); s1:=st(AB,BC,AC); s2:=st(CD,DA,AC); writeln('Ответ: ', s1+s2)end.

Задача 4. Найти максимальное из трех введенных чисел.

program max_func;
var a,b,c,m1,m2:real;

function max(a,b: real): real; {Описываем функцию max с формальными}
begin {параметрами A и B, которая принимает }

if a>b then max:=a {значение максимального из них }
else max:=b {Здесь a и b - локальные переменные }

end;
begin

writeln('Введите три числа');
readln(a,b,c);
writeln('Максимальным из всех является ', max(max(a,b),c))

end.

Рекурсия – это способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения обращается сама к себе.

С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужная подпрограмма уже написана. Наконец, шагу индукции соответствует вызов создаваемой рекурсивной подпрограммы.

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

В основе рекурсивного алгоритма лежит рекурсивное определение какого-то понятия. Например, о факториале числа N можно сказать, что N! = N*(N – 1)!, если N > 0 и N! = 1 если N = 0. Это – рекурсивное определение.

Вот еще одно рекурсивное определение.

1. 3 коровы – это стадо коров.

2. Стадо из n коров – это стадо из n – 1 коровы и еще одна корова.

Задача 5. Вычислить факториал числа n.

Чтобы получить значение факториала числа n, требуется умножить на n факториал числа (n - 1). Известно также, что 0! = 1 и 1! = 1.

var k: longint;l: byte;function fact(n: byte): longint;begin if (n = 0) or (n = 1) then fact:= 1 else fact:= n * fact(n - 1);

end;

begin write('l='); readln(l); k:=fact(l); writeln(‘k=’,k);end.

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

var x,y,z:integer;function plus(a,b: integer): integer; begin if b=0 then plus:=a else plus:=plus(a+1,b-1) end; begin write('x='); readln(x); write('y='); readln(y); z:=plus(x,y); writeln(z); readln end.

Задача 7. Вычислить N-е число Фиббоначчи. Числа Фиббоначчи строятся следующим образом: F(0)=F(1)=1; F(i+1)=F(i)+F(i-1); для i>=1.

program fib;

var n: byte;

function f(k:byte): word;

begin

if k<2 then f:=1 else f:=f(k-1)+f(k-2);

end;

begin

write('введите номер числа Фиббоначчи ');

readln(n);

writeln(n,'-е число Фиббоначчи =',f(n));

readln

end.

Задача 8. Найти максимальную цифру в записи данного натурального числа.

program max_c;

type cislo = 1..(high(longint));

zifra = 0..9;

var a: longint;

function maximum(n: longint): zifra;

begin

if n < 10 then maximum:= n

else if n mod 10 > maximum(n div 10) then maximum:= n mod 10

else maximum:= maximum(n div 10)

end;

begin

write('Введите натуральное число: ');

readln(a);

writeln('Максимальная цифра равна ', maximum(a))

end.

При создании функции maximum было использовано следующее соображение: если число состоит из одной цифры, то она является максимальной, иначе если последняя цифра не является максимальной, то ее следует искать среди других цифр числа. При написании рекурсивного алгоритма следует позаботиться о граничном условии, когда цепочка рекурсивных вызовов обрывается и начинается ее обратное «раскручивание». В нашем примере это условие n < 10.

Достоинством рекурсии является компактная запись, а недостатками - расход времени и памяти на повторные вызовы функции и передачу ей параметров, а, главное, опасность переполнения стека.

Рекурсивный вызов может быть косвенным, или неявным. Например, это происходит в случае, когда одна подпрограмма вызывает другую, а та в свою очередь –первую. При использовании такой программной конструкции необходимо опережающее описание процедур и функций с директивой forward. Сначала пишется только заголовок подпрограммы со словом forward, а реализация приводится ниже. При этом в ней можно писать в заголовке либо только имя подпрограммы, либо полностью повторять заголовок.

Пример: Неявная рекурсия.

procedure b(x:byte); forward;

procedure a(y:byte);

begin

b(y);

end;

pппппппппппппппппппппппппппппппппппппппппппппппппппппппппппппппппппппппrocedure b;

begin

a(x);

end;

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