Лекція №10
Тема: Рекурсивні функції і процедури, параметри-процедури
План заняття:
1. Рекурсивні функції і процедури
2. Параметри процедури
Рекурсивні функції і процедури
Деякі функції можна визначати рекурсивно. Наприклад, f(n)=n! можна визначити так:
n!=
Тобто це є визначенням функції через цю саму функцію, У мові Паскаль рекурсивний опис функції полягає в тому, що в тілі такої функції міститься звертання до цієї ж функції. Наведемо рекурсивний опис функції п!:
function FACT2(n: integer): integer;
begin
if n=0
then FACT2:=1
else FACT2:=n*FACT2(n-1)
end;
Зазначимо, що в лівій частині оператора присвоєння FACT2 не означає рекурсивності. Рекурсія є в правій частині, де наявне звертання до функції FACT2 з параметром п-1.
Під час обчислення FACT2(3), наприклад, відбувається послідовне вираження FАСТ3(3) через FACT2(2). FACT2(2) через FACT2(1), FACT2(1) через FACT2(0)=1. Тоді FACT2(1)=1; FACT2(2)=2*1=2; FACT2(3)=3*2=6;
У цьому випадку неявно вводяться додаткові змінні. Використання рекурсії робить програму компактнішою, однак потребує додаткового машинного часу і пам'яті.
Як і функції, рекурсивними можуть бути процедури. Ім'я рекурсивної процедури міститься в її тексті. Тобто процедура є рекурсивною, якщо вона викликає саму себе. Такий виклик процедур і функцій може виникнути внаслідок або рекурсивного опису, або рекурсивного звертання.
Рекурсивний опис полягає в тому, що у виконуваній частині процедури або функції міститься звертання до неї самої. Прикладом рекурсивного опису є розглянута функція обчислення факторіала. У випадку рекурсивного опису потрібна наявність базової частини опису, яка забезпечувала б завершення рекурсивних викликів функції або процедури. В наведеному прикладі такою базовою частиною, що забезпечує досягнення ситуації, коли FACT(n) не залежить від FACT(n-1), є визначення функції FACT(0)=1 при n=0.
Прикладом рекурсивного звертання може бути такий оператор:
J:=TR(N1 ,А1, B1,TR(N2, А2, В2, FN));
Тут ім'я функції TR використано як операнд в операторі присвоєння, а також як фактичний параметр цієї функції. Застосування рекурсивних процедур і функцій робить програму в цілому гнучкішою і наочнішою, однак часто менш ефективною.
Параметри-процедури
Як формальні параметри в мові Паскаль, крім параметрів-значень і параметрів-змінних, використовують також імена процедур і функцій.
Параметри-процедури в списку формальних параметрів в авторській версії Паскаль зазначають після службового слова procedure. Наприклад
procedure PR(i, j: integer; varz: real; procedure P);
Приклад використання параметрів-процедур (схематично)
program R;
var ar, br, cr: real;
procedure P(x, y: real);
begin
……
end; {P}
procedure Q(k, g: real);
begin
……
end; {Q}
Тут результат від процедур Р і Q повинен передаватися через глобальні змінні:
procedure T(procedure S(p, g: real); var a, b: real);
var c,d: real
begin
……
S(c+1,d/2)
……
end {T}
begin {R}
……
T(P, ar, br);
……
T(Q, br, cr);
……
end.{R}
У Турбо Паскалі використання параметрів-процедур дещо інше, зокрема, потрібно попередньо визначити процедурний тип:
type
Proc=procedure(T: real);