Рекурсія
Рекурсія– це звертання підпрограми до самої себе. Щоб таке звертання не було нескінченним, у тілі підпрограми повинне бути умова, по досягненні якого подальшого звертання не відбувається. Ця вимога є головною вимогою до рекурсивних процедур
Приклад рекурсивного обчислення факторіала:
Математично функція обчислення факторіала визначається так:
0!=1
n!=n*(n-1)!
Program Recurce;
{Функція для рекурсивного обчислення факторіала}
Function Factorial(N:Byte):Longint;
Begin
If N=0 then Factorial:=1
Else Factorial:=N*Factorial(N-1);
End;
BEGIN
WriteLn(Factorial(6));
END.
Форми рекурсивних підпрограм:
З виконанням дій на рекурсивному спуску(дії виконуються до рекурсивного виклику)
Приклад
Procedure Proc1;
Begin
дії;
If умова then Proc1;
End;
З виконанням дій на рекурсивному поверненні(дії виконуються після рекурсивного виклику)
Приклад
Procedure Proc2;
Begin
If умова then Proc2;
дії;
End;
З виконанням дій як на поверненні, так і на спуску.
Найчастіше рекурсивні підпрограми використовуються при обробці спискових або деревоподібних структур даних (Наприклад, при розробці трансляторів виконується побудова дерева розбору).
Зустрічається також непряма рекурсія. У цьому випадку перша процедура викликає другу, а друга – першу. При використанні непрямої рекурсії потрібно випереджальний опис – до заголовка процедури додається зарезервоване слово Forward.
Приклад непрямої рекурсії:
Procedure Test2; Forward;
Procedure Test1;
Begin
. . .
Test2;
. . .
End;
Procedure Test2;
Begin
. . .
Test1;
. . .
End;
Процедурні (функціональні) типи
У багатьох задачах обчислювальної математики необхідно передавати імена процедур і функцій як параметри. Наприклад, при обчисленні визначеного інтеграла по одному з відомих методів (трапецій, прямокутників і т.д.) можна скласти універсальну підпрограму, а функцію, що інтегрується, передавати в неї як параметр.
Для реалізації такого способу в Turbo Pascal уведений спеціальний тип – процедурний (чи функціональний).
Процедурний (функціональний) тип визначається в розділі опису типів як заголовок чи процедури функції зі списком формальних параметрів, але без вказівки імені.
Приклад оголошення процедурних (функціональних) типів
Type
ProcType=Procedure (a,b:Integer); {Процедурний тип}
FuncType=Function (x:Real):Real; {Функціональний тип}
Після оголошення процедурного (функціонального) типу його можна використовувати для опису формальних параметрів – імен процедур і функцій. При цьому необхідно також написати реальні процедури і функції, імена яких будуть передаватися як фактичні параметри. Ці процедури і функції повинні обов'язково компілюватися з далекою моделлю виклику (використовується ключове слово Far у заголовку чи процедури функції)
Приклад – Функція для
обчислення визначеного інтеграла
методом трапецій. Функція, що інтегрується,
передається як параметр.
Розрахункова формула обчислення
визначеного інтеграла по методу трапецій
де N– число ділянок розбивки;
h – величина інтервалу розбивки.
Текст програми
Program CalculateIntegral;
Uses CRT;
{Опис типу-функції}
Type
Func = Function (X:Real):Real;
{ Підінтегральна функція з далекою моделлю виклику }
Function Fn(X:Real):Real;Far;
Begin
Fn:=SQRT(X)+8;
End;
{Функція обчислення інтеграла по методу трапецій}
Function Integral(a,b:Real;N:Integer;Y:Func):Real;
Var
i:Integer;
h:Real;
S,R,X:Real;
Begin
h:=(b-a)/N;
S:=(Y(a)+Y(b))/2;
X:=a+h;
For i:=1 to N-2 do
Begin
S:=S+Y(X);
X:=X+h;
End;
Integral:=h*S;
End;
{Основна програма}
Var
Sm:Real;
BEGIN
ClrScr;
Sm:=Integral(0,5,1000,Fn);
WriteLn('Інтеграл=',Sm:10:3);
ReadLn;
END.