Рекурсии

ОБЛАСТЬ ДЕЙСТВИЯ ПАРАМЕТРОВ.

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

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

В Turbo Pascal допускается любой уровень вложенности процедур и функций. Процедура, описанная в основной программе, может иметь описания внутренних процедур и функций и т.д. При этом объекты, описанные в вызывающей процедуре, являются глобальными по отношению к вызываемой процедуре.

Для доступа к объектам, описанным в различных блоках, требуется соблюдение следующих правил:

1. Имена объектов, описанных в некотором блоке, считаются известными в пределах данного блока, включая и все вложенные блоки.

2. Имена объектов, описанных в блоке, должны быть уникальны в пределах данного блока и могут совпадать с именами объектов из других блоков.

3. Если в некотором блоке описан объект, имя которого совпадает с именем объекта, описанного в объемлющем блоке, то это последнее имя становится недоступным в данном блоке (оно как бы экранируется одноименным объектом данного блока).

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

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

Пример 6: Вычислить факториал натурального числа. Для того, чтобы вычислить N!, надо знать значение (N-1)! и умножить его на N, при этом 1!=1. В общем виде это можно записать так:

Решение:

program pr6;

var n,f:integer;

function fact(n:integer):integer;

begin

if n=1 then fact:=1

else fact:=n*fact(n-1)

end;

begin

writeln(‘Ввести число n>1’);

read(n);

f:=fact(n);

writeln(‘Для числа ‘,n,’ значение факториала =’,f)

end.

Пусть n=5, т.е. вычислить 5! Как же будет вычисляться факториал этого числа? Первый вызов этой функции будет из основной программы. Надо заметить, что при каждом обращении к функции будет появляться свой набор локальных переменных со своими значениями, в данном случае – переменная n, для которых выделяется память. А после завершения работы эта часть памяти освобождается, и переменные удаляются.

Так как n, то пойдем по ветке else и fact присваиваем значение n*fact(n-1), т.е. надо умножить 5 на значение функции fact(4). Поэтому обращаемся второй раз к этой же функции, но передаем ее новое значение параметра – 4. Так делаем до тех пор, пока не передадим значение равное 1. Тогда n=1, а поэтому значение функции fact:=1. Таким образом, n=1 – это условие, по которому процесс входа в следующую рекурсию заканчивается. Идет возвращение в точку возврата и подстановка в оператор присваивания значения вычисленной функции. Т.е. возвращаемся в предыдущую функцию для n=2: fact:=n*fact(n-1), значит, fact:=2*1, следовательно, fact(2)=2. И возвращаемся дальше. Таким образом, получаем значение fact(5)=120, это значение и присваивается переменной f.

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

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

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Задача 1.

Составьте программу подсчета числа всех натуральных чисел, меньших М, квадрат суммы цифр которых равен Х.

Задача 2.

Даны действительные числа S, T. Составить программу вычисления выражения

, где .

Задача 3.

Вычислить сумму: 1!+2!+3!+ … +n!, используя функцию вычисления факториала числа k!

Задача 4.

Даны координаты вершин многоугольника (х1,y1,x2,y2,…,x10,y10). Определить его периметр (вычисление расстояния между вершинами оформить подпрограммой).

Задача 5.

Даны координаты трех вершин треугольника АВС и даны координаты четвертой точки D. Определить, является ли эта точка внутренней точкой треугольника.

Задача 6.

Даны координаты вершин двух треугольников. Найти длины всех сторон этих треугольников.

Задача 7.

Дано натуральное число n>2. Выяснить, имеется ли среди чисел n, n+1, …, 2n близнецы, т.е. простые числа разность между которыми равна двум.

Задача 8.

Составить программу вычисления значений функции Аккермана для неотрицательных чисел n и m.

Задача 9.

Найти первые N чисел Фибоначчи. Каждое число Фибоначчи равно сумме двух предыдущих чисел при условии, что первые два равны 1 (1, 1, 2, 3, 5, 8, 13, 21, …), поэтому в общем виде n-е число можно определить так:

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что называется подпрограммой? В чем состоит сходство и различие подпрограмм-процедур и подпрограмм-функций в языке Turbo Pascal?

2. В чем различие между стандартными и определенными пользователем подпрограммами?

3. Запишите синтаксическую диаграмму определения процедуры, функции.

4. Опишите последовательность событий при вызове процедуры или функции.

5. Что называется параметром, и каково его назначение? Формальные, фактические параметры, их взаимосвязь.

6. Каковы отличия параметров-значений от параметров-переменных, особенности их описания и применения.

7. Каковы особенности параметров-процедур и параметров-функций?

8. Чем отличаются локальные и глобальные параметры? Какова область их действия?

9. Что такое рекурсия?

10. Даны фрагменты программ:

а) var c,d:integer; б) var c,d:integer;

procedure P(x,y:integer); procedure Q(x:integer; var y:integer);

begin begin

y:=x+1 y:=x+1

end; end;

в) var c,d:integer;

procedure R(var x,y:integer);

begin

y:=x+1

end;

а) для каждой из этих процедур указать, какие из ее параметров являются параметрами-значениями, а какие – параметрами-переменными.

б) определить, что будет выдано на печать в следующих случаях:

c:=2; d:=0; P(sqr(с)+c, d); writeln(d);

c:=2; d:=0; Q(sqr(с)+c, d); writeln(d);

Почему при изменении в процедуре параметра-значения соответствующий фактический параметр не меняет своего значения? Что надо сделать, чтобы он менял значение?

в) допустимы ли обращения R(sqr(c)+c, d) и R(c,d)? Почему невыгодно объявлять параметр, не меняющийся в процедуре, параметром-переменной?

11. Что будет напечатано следующей программой?

а) program dem1; б) program dem2;

var x,y:char; var a,b,c,d:integer;

procedure P(x:integer); procedure P(var b:integer; c:integer);

const y:true; var d:integer;

begin begin

writeln(x,’ ‘,y); a:=5; b:=6; c:=7; d:=8;

end; writeln(a,b,c,d);

procedure Q(x:integer); end;

var x:char; begin

begin a:=1; b:=2; c:=3; d:=4;

x:=succ(y); P(a,b); writeln(a,b,c,d)

y:=’*’; end.

writeln(x,’ ‘,y)

end;

begin

x:=’a’; y:=’5’;

P(8); writeln(x,’ ‘,y);

Q;

writeln(x, ‘ ‘,y)

end.

Дата добавления: 2014-01-04