Proceduri i funcii recursive

Definiie

Recursia se definete ca o situaie n care un subprogram se autoapeleaz fie direct, fi prin intermediul altei funcii sau proceduri. Subprogramul care se autoapeleaz se numete recursiv.

De exemplu

Funcia factorial

= 1, = 0

1 , > 0

Poate fi exprimat n PASCAL, urmnd direct definiia, n forma:

function F(n:integer):longint;

Begin

if n=0 then F:=1

else F:=n*F(n-1);

End;

Efectul unui apel F(7) este declanarea unui lan de apeluri ale funciei F pentru parametrii actuali 6,5,,1,0:

F(7) -> F(6) -> -> F(1) -> F(0).

Apelul F(0) determin evaluarea direct a funciei i oprirea procesului repetitiv; urmeaz revenirile din apeluri i evaluarea lui F pentru 1,2,,6,7 ultima valoare fiind ntoarcerea n locul primului apel.

Program fact_rec;

var i,n:integer;

function

fact(n:integer):longint;

Begin

if n=0 then fact:=1

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

End;

begin

writeln('Introduceti n');

readln(n);

writeln('Factorial de ',n,'

este ',fact(n));

end.

Introduceti n7Factorial de 7 este 5040

Funcia

= 0, = 01, = 1

1 + 2 , > 1

Are ca valori numerele Fibonacci. Urmnd definiia, obinem:

function Fib(n:integer):longint;

begin

if n=0 then Fib:=0

else if n=1 then Fib:=1

else Fib:=Fib(n-1)+Fib(n-2);

end;

Fiecare apel al funciei Fib pentru n>1 genereaz dou apeluri Fib(n-1), Fib(n-2) .a.m.d., de exemplu:

Fib(4) -> Fib(3), -> Fib(2) -> Fib(2), Fib(1), Fib(1), Fib(0) -> Fib(1), Fib(0).

Din exemplele n studiu se observ c recursia este util pentru programarea unor calcule repetitive. Repetiia este asigurat prin execuia unui subprogram care conine un apel la el nsui: cndexecuia ajunge la acest apel, este declanat o nou execuie .a.m.d.

Evident, orice subprogram recursiv trebuie s includ condiii de oprire a procesului repetitiv. De exemplu, n cazul funciei factorial procesul repetitiv se oprete cnd n ia valoarea 0; n cazul funciei Fibprocesul se oprete cnd n ia valoarea 0 sau 1.

Program Fib_rec;

var i,n:integer;

function fib(k:integer):longint;

begin

if (k=1) or (k=2) then fib:=1

else fib:=fib(k-1)+fib(k-2);

end;

begin

writeln('Introduceti n');

readln(n);

for i:=3 to n do

begin

writeln('Fib[',i,']=',fib(i));

writeln('R[',i,']=',fib(i)/fib(i-1):10:10);

end;

readln;

end.

Introduceti n5Fib[3]=2R[3]=2.0000000000Fib[4]=3R[4]=1.5000000000Fib[5]=5R[5]=1.6666666667

La orice apel de subprogram n memoria calculatorului vor fi depuse urmtoarele informaii:

- Valorile curente ale parametrilor transmii prin valoare;

- Locaiile (adresele) parametrilor-variabil;

- Adresa de retur, adic adresa instruciunii ce urmeaz dup apel.

Prin urmare, la apeluri recursive spaiul ocupat din memorie va crete rapid, riscnd depirea capacitii de memorare a calculatorului. Astfel de cazuri pot fi evitate, nlocuind recursia prin iteraie (instruciunile for, while, repeat). Pentru exemplificare prezentm o form nerecursiv a funciei factorial:

function F(n:integer):integer;

var i,p:Natural;

begin

p:=1;

for i:=1 to n do p:=p*i;

F:=p;

end;

Recursia este deosebit de util n cazurile n care elaborarea unor algoritmi nerecursivi este foarte complicat: translatarea programelor PASCAL n limbajul cod-main, grafica pe calculator, recunoaterea formelor .a.

Recursia indirect

Toate subprogramele recursive prezentate pn acum includ n partea executabil un autoapel, motiv pentru care se spune c s-a folosit recursia direct. Exist ns situaii n care un subprogram trebuie autoapelat prin intermediul altui subprogram, adic apare recursia indirect.

Exemplu

= 1, = 0

+ 1 , > 0

= 2, = 0

+ 1 , > 0

Evident, n textul PASCAL al funciei f(x) se va utiliza apelul g(x-1), iar n textul g(x) se va utiliza apelul f(x-1).

Conform regulilor de baz ale limbajului PASCAL, locul de definiie al unui nume trebuie s precede textual utilizrile numelui respectiv. n cazul funciilor f(x) i g(x), oricare ar fi forma textual a programului, numele uneia dintre funcii apare naintea locului de definire. Pentru a soluiona astfel de probleme, se utilizeaz declaraiile anticipate de subprograme.

O declaraie anticipat include antetul subprogramului i directiva forward(nainte). Corpul subprogramului apar textual undeva mai jos i este precedat de antet redus n care se specific doar numele subprogramului, fr parametri i tipuri.

ExempluProgram P115;var n:integer;{ Declaratii anticipate }function F(x : integer) : integer;forward; { declaratia anticipata a functiei F }function G(x : integer) : integer;beginif x=0 then G:=2

else G:=x+F(x-1);end; { G }function F(x : integer) : integer;begin { corpul functiei F }if x=0 then F:=1

else F:=x+G(x-1);end; { F }beginwriteln('Introduceti n: ');readln(n);writeln('Rezultatul este ', F(n));readln;end.

Introduceti n: 5Rezultatul este 17

n principiu, declaraiile anticipate pot fi folosite pentru definirea oricror proceduri sau funcii, nu neaprat recursive. Menionm ns c utilizarea nejustificat a declaraiilor anticipate complic structura de bloc a programelor PASCAL.

Exemplu

Aplicnd recursivitatea indirect s se determine valorile funciilor

= 2, 3

2 , 3 < 6 1 , > 6

= ( + 1)2, < 0

+ 5, 0 < 5 1 1, 5

= 2, < 0

+ 1 , 0 < 5 + 1 , 5

program a_b_c_ind;var x:integer;function a(x:integer):integer;forward;function b(x:integer):integer;forward;function c(x:integer):integer;begin

if x=0) and (x=5 then c:=b(x+1);

end;function a(x:integer):integer;begin

if x3) and (x6 then a:=c(x-1);end;

function b(x:integer):integer;begin

if x=0) and (x=5 then b:=c(-1)-1;end;begin

writeln('Introduceti x: ');

readln(x);writeln('a(',x,')=

',a(x),' ... b(',x,')= ',b(x),' ... c(',x,')= ',c(x));

readln;end.

Introduceti x: 5a(5)= 14 ... b(5)= 0 ... c(5)= 0

Pentru acas

Utiliznd recursia direct scriei un subprogram recursiv care calculeaz:

Suma S(n)=1+3+5++(2n-1)

= 0, = 0

1 + 2 1, > 0

Utiliznd recursia indirect scriei un subprogram recursiv care calculeaz:

= 1, = 0

1 + 1 , > 0

= 2, = 0

1 + 1 , > 0

= 3, = 0

1 + 1 , > 0