1.3. Рекурсивные процедуры.

Рекурсия (рекурсивная процедура или функция) возникает, если функция или процедура вызывает саму себя. Прямая рекурсия может вызывать себя непосредственно, например:

function Factorial (n: LongInt) : LongInt;

begin

Factorial:=n*Factorial(n-1);

end;

Рекурсивная процедура также может вызывать себя косвенно, вызывая вторую процедуру, которая, в свою очередь, вызывает первую:

procedure Ping(n: Integer);

begin

Pong(n-1);

end;

procedure Pong(n: Integer);

begin

Ping(n div 2);

end;

Классическим примером рекурсии является вычисление факториала. Факториал числа - это произведение целых чисел от 1 до : . Приведенное выражение можно переписать следующим образом:

Рекурсивная функция вычисления факториала:

function Factorial (N: Integer): Integer;

begin

if (N<=0) then

Factorial := 1

else

Factorial=N*Factorial(N-1);

end;

Функция сначала проверяет число на условие . Для чисел, меньших нуля факториал не определен, но это условие проверяется для подстраховки. Если бы функция проверила только условие равенства числа нулю, то для отрицательных чисел рекурсия была бы бесконечной.

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

Существуют два фактора, которые гарантируют, что эта рекурсивная функция в конце концов остановится. Во-первых, при каждом последующем вызове значение параметра N уменьшается на единицу. Во-вторых, значение N ограничено нулем. Когда значение достигает 0, функция заканчивает рекурсию. Такое условие, как , которое останавливает рекурсию, называется основным условием или условием остановки.

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

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

2. Порядок выполнения работы.

Изучить операторы, используемые для организации подпрограмм, выполнить контрольные примеры и задания соответствующего варианта.

Контрольный пример 1: Написать программу вычисления выражения , в котором возведение в степень выполняется функцией Step.

Решение.

1. Открыть новый проект Delphi: File – New Application .

2. Установить с помощью Object Inspector следующие свойства компонента Form1:

Form1.Height = 345

Form1.Width = 396

Form1.BorderIcons

biMaximize = false

Form1.BorderStyle = bsSingle

Form1.Position = poScreenCenter

Form1.Caption = 'Контрольный пример 1'.

3. Расположить на форме следующие компоненты: три компонента Edit, три компонента Label, один компонент Button. Установить с помощью Object Inspector для них следующие свойства:

Label1.Caption = 'A'

Label2.Caption = 'M'

Label3.Caption = 'Z'

Edit1.Text = ''

Edit2.Text = ''

Edit3.Text = ''

Button1.Caption = 'Выполнить'.

Результат показан на рисунке 1:

Рис. 1

4. Текст программы приведен ниже:

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Edit1: TEdit;

Label1: TLabel;

Label2: TLabel;

Edit2: TEdit;

Button1: TButton;

Label3: TLabel;

Edit3: TEdit;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

M:integer;

A,Z,R:real;

implementation

{$R *.dfm}

// Функция вычисления степени.

// N,Х – формальные параметры,

// результат, возвращаемый функцией в точку вызова

// имеет вещественный тип.

function Step(N:integer; X:real):real;

var i:integer; y:real;

begin

y:=1;

for i:=1 to N do

y:=y*x;

step:=y; // присваивание функции результата

// вычисления степени

end; // Step

procedure TForm1.Button1Click(Sender: TObject);

begin

// ввод значения числа А и показателя степени М

A:=StrToFloat(Edit1.Text);

M:=StrToInt(Edit2.Text);

// Вызов функции с передачей ей фактических параметров

Z:=Step(5,A);

Z:= Z+Step(3,1/A);

if M=0 then R:=1

else if M>0 then R:=Step(M,A)

else R:=Step(-M,1/A);

Z:=Z/(2*R);

Edit3.Text:=FloatToStrF(Z,fffixed,7,5);

end;

end.

5. Запустить программу на компиляцию и выполнение.

6. Результаты работы программы приведены на рисунке 2:

Рис. 2.

Контрольный пример 2. Напишите процедуру, которая по заданному интервалу и функции определяет «ноль» функции с заданной точностью, используя метод деления отрезка пополам. Известно, что на границах интервала функция принимает значения, отличные по знаку. Определите «ноль» функции (наименьший положительный корень) на произвольном интервале . Числа и вводятся с клавиатуры.