recurenta versus iteratiefmi.unibuc.ro/ro/pdf/2012/admitere/reciter_7apr12.pdf · 2015-05-25 · 2...

1

RECURENTA VERSUS ITERATIE

Facultatea de Matematica si Informatica,

Universitatea din Bucuresti

7 aprilie 2012

2

Noţiunea de algoritm = notiune primară.Există descrieri şi proprietăţi:

Un algoritm constă dintr-o mulţime finită de paşi, fiecare necesitânduna sau mai multe operaţii.

Pentru a fi implementate pe un calculator, într-un anumit limbaj deprogramare, aceste operaţii trebuie să fie:

definite;

efective.

Caracteristicile algoritmilor

corectitudinea;

finititudinea:;

generalitatea;

completitudinea;

claritatea.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

3

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Studiul algoritmilor cuprinde mai multe aspecte (1):

Elaborarea algoritmilor.

Tehnici de elaborare (reguli) + creativitate (intuiţie) = soluţie

Exprimarea algoritmilor

- scheme logice, limbaje de tip pseudocod, programe in diferite

limbaje de programare.

- se impune utilizarea unui anumit stil de programare (legat nu de un

anumit limbaj de programare, ci de tipul limbajului şi de modul de

abordare)

4

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Studiul algoritmilor cuprinde mai multe

aspecte (2):

Validarea algoritmilor (demonstrarea

matematica a corectitudinii, independent de

implementare).

Analiza algoritmilor. (in general: timpul de

calcul şi/sau la memoria necesară)

Testarea programelor :

(i) depanarea (debugging) Cf. E.W.

Djikstra, prin depanare putem evidentia

prezenta erorilor dar nu si absenta lor!

(ii) verificare (profiling)

5

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Incercarea de definire (decada 1930-1940):

Sunt propuse diverse formalisme pentru

notiunea de algoritm:

Functiile -calculabile (Alonzo CHURCH şi

Stephen Cole KLEENE);

Masinile Turing (Alan TURING);

Functiile general recursive (Kurt GÖDEL);

Sistemele Post, inclusiv masina Post-Turing

(Emil Leon POST);

Algoritmii normali Markov (N.N. MARKOV)

Toate teoriile: echivalente

Teza Church-Turing (cele 2 variante)

6

Lambda calculul

O λ-functie este definită de o lambda-expresie care

exprimă acţiunea funcţiei în argumentele ei.

Exemple: funcţia f(x)=x+2: λ x. x + 2 .

numărul f(3): (λ x. x+ 2) 3

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

7

Masina Turing

a b a b ┴ ┴ ┴

unitate de

control

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

8

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

9

Maşina Turing

Un sistem ( , , Q, q0, F, ) unde:

este o mulţime finită, nevida numită alfabet de intrare;

este o mulţime finită, nevida numită alfabetul benzii;

, şi ;

Q este o mulţime finită, nevida numită mulţimea stărilormasinii;

q0 Q este starea iniţială;

F Q este mulţimea stărilor finale (de acceptare sau derespingere);

: Q x Q x x { L , R } este funcţia de tranziţie, unde Ldenota deplasarea la stânga iar R denota deplasarea ladreapta a cursorului masinii.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

10

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Stephan Cole KLEENE: "The Theory of Recursive

Functions, Approaching its Centennial", Bulletin (New

Series) of the American Mathematical Society, Vol. 5,

No. 1, July 1981:

"părinţi" teoriei funcţiilor recursive (inafara lui Kurt Gödel şi

Kleene însuşi) sunt consideraţi a fi:

Leopold Kronecker, prin conferinţa ţinută pe 21

sept. 1886 în faţa Der Deutschen

Naturforscherversammlung zu Berlin (Asociaţia

pentru Cercetarea Naturii), cf. H. Weber, Leopold

Kronecker, Math. Ann. 43 (1893), 1-25

Julius Wilhelm Richard Dedekind (1831–1916),

prin Teorema 126 ("Satz der Definition durch

Induktion") din articolul "Was sind und was sollen

die Zahlen? (Ce sunt şi ce ar trebui sa fie

numerele)" publicat în 1888 si prin Definitia 71

(care contine defiinitia axiomatica a N i.e.

axiomele Dedekind-Peano)

11

Exemple de functii primitiv recursive:

a+0 = a

a+succ(x) = succ(a+x)

a ∙0 = 0

a ∙ succ(x) = a ∙ x+a

a 0 = 1

a succ(x) = a x ∙ a

unde succ(x)=x+1 .

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

12

Recurenta primitiva

Fie funcţiile : g : N n N , h : N n+2 N ;

se cere să se construiască funcţia

f : N n+1 N

care să satisfacă următoarele două ecuaţii :

(1) f(a1 ,a2 ,…, an ,0) = g(a1 ,a2 ,…, an) ,

(2) f(a1 ,a2 ,…, an , x+1) = h(a1 ,a2 ,…, an , x , f(a1 ,a2 ,…, an , x)) .

Spunem că f este definită prin recurenţă primitivă asupra lui x din

funcţiile g şi h , prin intermediul a n>=0 parametri a1 ,a2 ,…, an .

Convenim ca în cazul n=0 să notăm prin g o constantă număr

natural.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

13

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Compunerea functionala

Fie n , m două numere naturale.

Se dau m+1 funcţii de n argumente:

h : N m → N , g i : N n → N , 1 ≤ i ≤ m

Funcţia

f : N n → N

este definită prin compunere funcţională din funcţiile h , g1 , g2 ,…, gm

dacă şi numai dacă:

f(x1 ,x2 ,…, xn ) = h (g1(x1 ,x2 ,…, xn ), g2(x1 ,x2 ,…,xn ),…,gm(x1 ,x2 ,…, xn

))

Un caz particular de compunere functionala:

subtitutia (m=1)

14

f(a1 ,a2 ,…, an ,0) = g(a1 ,a2 ,…, an) ,

f(a1 ,a2 ,…, an , x+1) = h(a1 ,a2 ,…, an , x , f(a1 ,a2 ,…, an , x)) .

f(x1 ,x2 ,…, xn ) = h(g1(x1 ,x2 ,…, xn ), g2(x1 ,x2 ,…,xn ),…,gm(x1 ,x2 ,…, xn ))

Exemplul 1:sum(a,x) = a+x,

=> n=1, a1=a

=> sum (a,0) = a+0 = a => g(a) = a = p1(1)(a) ,

sum(a,x+1)=a+(x+1)=(a+x)+1

=>h(a,x,y)=succ(sum(a,x))=succ(p3(3)(a,x,sum(a,x))).

=> sum(a,0)=p1(1)(a) ,

sum(a,x+1)=h(a,x,sum(a,x)) , unde h:N3 N , h(a,x,y)=(succ0p3(3))(a,x,y).

Exemplul 2:|x-y| = max(0,x-y)+max(0,y-x),

=> |x-y|= max(0, P(2)1 (x,y)-P(2) 2(x,y)) + max(0, P (2) 2(x,y)-P(2)1(x,y)).

15

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Exemplul 3:

O funcţie general recursivă: funcţia Ackermann-Peter:

int ack(int m, int n)

{

if (0==m) return n+1;

if (0==n) return ack(m-1,1);

return ack(m-1,ack(m,n-1));

}

altfelnmackmack

nmack

mn

nmack

)),1,(,1(

0),1,1(

0,1

),(

16

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Exemplul 4 (Conjectura lui Collatz, 1937)

Se dă şirul de numere a0 ,a1 ,…,an , … definit prin

iteraţia pură:

Pentru orice număr natural a există un index n astfel

încât

an=1

Verificata pe calculator pana la 20 × 258 ≈ 5.764 × 1018

.,13

,,2/1

0

altfela

paresteadacaaa

aa

n

nnn

17

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Functia lui COLLATZ :

este definita prin:

f(n)= n/2, daca n este par,

f(n)= 3*n+1, daca n este impar

şi are urmatoarele propretati:

lungimea secventei de numere generata in vederea atingerii valorii 1 unse poate calcula pintr-o formula bazata pe datele de intrare

tinde catre 1.

Se cere sa se scrie un program care sa citeasca o pereche de valori naturale nenule,reprezentand primul si ultimul numar intr-o secventa inchisa de numere naturale.

Pentru fiecare astfel de secventa inchisa, se cere sa se deteremine valoarea caregenereaza cea mai lunga serie cu functia de mai sus, inainte de a ajunge la 1.

Cea mai mare valoare din secventa si din sirul transformarilor nu va depasi tipul long.

http://gfredericks.com/math/Arith/collatzPage.html

18

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

#include <iostream.h>

long int length (long int n)

{

long int aux=1;

if (n%2) n=n*3+1; else n/=2;

while(n-1){

if (n%2) n=n*3+1; else n/=2;

aux++;

}

return aux;

}

void main ()

{

long int n,m,max,l,i;

cin>>n>>m; max=0; l=-1;

for (i=n; i<=m; i++)

if (length(i)>l) {

max=i; l=length(i);

}

cout<<"intre "<<n<<" si "<<m<<" ,"<<max<<" are lungimea maxima"<<l<<endl;

}

Intre 1 si 20 , numarul 18 are ofera lungimea maxima: 20

19

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Mulţimea funcţiilor de bază

este formată din:

funcţia succesor succ : N N , succ(x)=x+1

funcţiile constante ca(n): N n N , ca

(n) (x1 ,x2 ,…, xn )=a

funcţiile proiecţie pi(n): N n N , pi

(n) (x1 ,x2 ,…, xi ,…, xn )= xi ,

unde a , n , m N , 1 i n, 1jn.

20

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Clasa funcţiilor primitiv recursive

este cea mai mică familie de funcţii f : N n → N , n>=1,

care

conţine mulţimea funcţiilor de bază şi

este închisă faţă de operaţiile de

compunere funcţională şi

recurenţă primitivă.

Dedekind (1888) şi Peano (1889),

Skolem: (1923),

Gödel (1931),

Peter (1934).

21

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Următoarele funcţii si predicate sunt primitiv recursive:

a) f:N 2N , f(x,y)=x+y

b) f:N 2N , f(x,y)=x*y

c) f:N 2N , f(x,y)=xy , (x0=1)

d) pd:NN , pd(x)=max(0,x-1)

e) f:N 2N , f(x,y)=max(0,x-y) , (diferenţa aritmetică)

f) sg:NN , sg(0)=0 , sg(x)=1, x>0 ,

g) f:N2N , f(x,y)=|x-y| , (modulul)

h) sqrt:NN ,

i) ls,gr,eq:N 2{0,1}, ls(x,y)=1, daca x<y, ls(x,y)= 0, altfel

gr(x,y)=1, daca x>y, gr(x,y)=0, altfel

eq(x,y)=1, daca x=y, eq(x,y)=0, altfel

xxsqrt )(

22

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Scheme de recurenţă speciale:

recurenţa ereditară

recurenţa simultană

23

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Schema de recurenţă ereditară

Exemplu:

Considerăm şirul lui Fibonacci:

u0=u1=1 ,

un+2=un+1+un.

24

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Limbajul Borland Pascal

{fib1.pas : implementarea rec. }

function Fib (n: integer): integer;

{returneaza al n-lea termen din

sirul lui Fibonacci, n0}

begin

if (n<=1) then Fib := n

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

end;

Limbajul C/C++

//fib1.cpp : implementarea rec.

long Fib (long n)

// returneaza al n-lea termen al

sirului lui Fibonacci, n0

{

if (n<=1) return n;

else return Fib (n-1) + Fib (n-2);

}

25

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Limbajul Borland Pascal

{fib2.pas: implementarea iterativa}

function Fib (n: integer): integer;

var crt, old, older : integer;

begin

old : = 1; older : = 0;

while (n > 1) do

begin

crt : = old +older;

older : = old;

dec(n)

end;

end;

Limbajul C/C++

// fib2.cpp : implementarea iterativa

long Fib (long n)

{

if (n<=1) return n;

long crt, old=1, older=0;

while(n-- >1)

{

crt = old +older;

older = old;

}

return crt;

}

26

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Definitie

Fie x0, x1,…, xk N. Numarul natural

se numeste numărul Gödel asociat şirului (x0, x1,…,x k) şi

se notează cu <x0,x1,…,xk>.

Exemple: <3,1,2> = 23∙31∙52 = 600,

<1,2,0,5> = 21∙32∙50∙75 = 2898918

Definiţie:

Funcţia f:Nn+1 N se obţine prin recurenţă ereditară din funcţiile

g : Nn N şi h : Nn+2

N dacă:

f(x ,0) = g(x) ,

f(x ,y+1) = h(x ,y ,<f(x ,0) ,…, f(x ,y)>) ,

unde xNn iar <…> desemneaza numarul Gödel asociat

sirului f(x,0), … ,f(x,y).

kx

kpx

px

pn ...11

00

27

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Teoremă:

Clasa funcţiilor primitiv recursive este închisă faţă de

recurenţa ereditară.

Corolar:

Funcţia f: N N, f(n) = un este primitiv recursivă.

28

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Schema de recurenţă simultanăExemplu:

Considerăm ecuaţia lui Pell:

x2-dy2=1, unde x,y N , a>1, d=a2-1.

Propoziţie:

Perechea (x,y) N 2 este o soluţie pentru ecuaţia lui Pell

dacă există un număr n≥0 astfel încât

x = xn , y = yn , unde :

x0 = 1, y0 = 0 ,

xn+1 = a.xn + d.yn ,

yn+1 = xn + a.yn , x 0 .

29

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

program rec_indirecta;

var a,d,n: integer;

function y (n: integer): integer; forward;

function x (n: integer): integer;

begin

if n=0 then x:=1

else x:=a*x(n-1)+d*y(n-1)

end; {x}

function y (n: integer): integer;

begin

if n=0 then y:=0

else y:=x(n-1)+a*y(n-1)

end; {y}

begin {programul principal}

writeln ('dati constanta a > 1 si ordinul solutie n = '); readln (a,n);

d := a *a - 1;

writeln ('perechea de solutii de ordinul ',n,' este: (',x(n):4,' , ',y(n):4,').');

readln;

end.

30

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Definiţie:

Funcţiile fi : N n+1 N, (i=1,2) sunt definite prin recurenţă simultană

din funcţiile gi : N n N şi hi : N n+3 N (i=1,2) dacă

fi(x,0)=gi(x),

fi(x,y+1)=hi(x, f1(x,y), f2(x,y)) , (i=1,2).

Teoremă:

Clasa funcţiilor primitiv recursive este închisă faţă de recurenţa

simultană.

Corolar:

Funcţiile f1,f2: N N, f1(n) = xn, f2(n)=yn sunt primitiv recursive.

31

Conceptul de subprogram de tip funcţie cu apel recursiv.

Forma generală a unui subprogram de tip funcţie recursiv:

function f()

{

calcul initial;

conditie de oprire;

apel recursiv f();

calcul final;

return rezultat;

}

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

32

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Tipuri de subprograme recursive

(1) bazate pe funcţii (primitiv) recursive unare, (funcţia se apelează pe ea însăşi în mod

direct, ca în cazul calculării factorialului);

(2) bazate pe funcţii (primitiv) recursive de mai multe argumente (ca în cazul calculării

cmmdc pentru două numere naturale);

acestea sunt cunoscute sub numele de recursivitate liniară directă:

int cmmdc1 (int x, int y)

{ if (x==y) return x;

else

if (x>y) return cmmdc1(x-y, y);

else return cmmdc1(x, y-x);

}

int cmmdc2 (int x, int y)

{if (0==y) return x;

else

return cmmdc2(y, x%y);

}

33

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

(3) bazate pe funcţii care se apelează una pe alta (recursivitateasimultana, numita si recursivitate indirectă), ca in cazul calculariisolutiilor ecuatiei lui Pell: x2-dy2=1, unde x,y N , a>1, d=a2-1),

int x(int n)

{

if (n==0) return 1;

return a*x(n-1)+d*y(n-1);

}

int y(int n)

{

if (n==0) r eturn 0;

return x(n-1)+a*y(n-1);

}

34

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

(4) bazate pe funcţii care au nevoie de mai multe valori anterioare pentru

a calcula valoarea curentă (recursivitatea ereditara, numita si

recursivitatea neliniară sau în cascadă), ca în cazul determinării unui

element al şirului lui Fibonacci după formula:

int fibonacci (int n)

{

if (n<=1) return 1;

return fibonacci(n-1) + fibonacci(n-2);

}

35

Un subprogram recursiv trebuie să respecte următoarele

reguli:

1. subprogramul trebuie să poată fi executat, cel puţin într-o

situaţie, fără a se autoapela;

2. subprogramul recursiv se va autoapela într-un mod în care se

tinde spre ajungerea în situaţia de execuţie fără autoapel.

Pentru a permite apelarea recursivă a subprogramelor

limbajele de programare dispun de mecanisme speciale

de suspendare a execuţiei programului apelant,

de salvare a informaţiilor necesare şi

de reactivare a programului suspendat.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

36

Pentru implementarea recursivităţii se foloseşte o stivă.

La fiecare apel recursiv al unuisubprogram se salvează în stivă stareacurentă a execuţiei sale (adresa derevenire şi contextul programului).

Stiva implicita = zona de memorie

în care se poate face salvarea

temporară a unor valori, organizată

după principiul LIFO

Adresa de revenire = adresa

instrucţiunii cu care va continua

programul întrerupt la reluarea

execuţiei sale

Context = valorile variabilelor locale

subprogramului, valorile parametrilor

de tip valoare şi adresele parametrilor

de tip referinţă

37

Deşi variabilele locale ale subprogramului apelat au aceiaşi

identificatori cu cei ai subprogramului apelant, orice referire la

aceşti identificatori se asociază ultimului set de variabile alocate

în stivă.

Zona din stivă rămâne alocată pe tot parcursul execuţiei

subprogramului apelat şi se dealocă în momentul revenirii în

programul apelant.

Stiva nu este gestionată explicit de programator ci de către

limbaj.

La terminarea execuţiei subprogramului apelat recursiv se

reface contextul programului din care s-a făcut apelul.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

38

Datorită faptului că la fiecare autoapel se ocupă o zonă de

stivă, recursivitatea este eficientă numai dacă numărul de

autoapeluri nu este mare, astfel încât să nu se ajungă în situaţia

umplerii stivei.

Recursivitatea oferă avantajul unor soluţii mai clare pentru

probleme şi unei lungimi mai mici a programelor.

Ea prezintă însă dezavantajul unui timp mai mare de execuţie

şi a unui spaţiu de memorie ocupat mai mare.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

39

Ce se întâmplă la autoapelul funcţiei/procedurii?

Prin autoapelul funcţiei/ procedurii instrucţiunile

rămân neschimbate.

Procedura/funcţia va prelucra datele transmise în stivă.

In cazul unui nou autoapel, se creează un nou nivel

pentru stivă, în care se depun noile valori.

Procedura/funcţia care s-a autoapelat se reia de la

instrucţiunea care urmează autoapelului şi va lucra cu

variabilele (valorile) reţinute în stivă în momentul

autoapelului, la care se adaugă valorile returnate.

La atingerea unuia dintre cazurile de bază (condiţia de

oprire), urmează să se revină din autoapelări.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

40

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Demonstrarea corectitudinii algoritmilor recursivi:

se face intr-un mod similar demonstrarii corectitudinii

algoritmilor nerecursivi;

este mult simplificată de forma algoritmului (care permite

utilizarea comodă a metodei inducţiei matematice

complete):

se verifică mai întâi dacă toate cazurile particulare (de

terminare a apelului recursiv) funcţionează corect;

se trece apoi la o verificare formală, prin inducţie, a

funcţiei recursive corespunzătoare, pentru restul cazurilor.

41

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Exemplificare: calculul factorialului unui număr

int factorial (int n)

{

if (0==n) return 1;

return n*factorial(n-1);

}

Demonstrarea corectitudinii: doi pasi:

pentru n = 0, valoarea 1 returnată de program este corectă;

dacă n>1 atunci, presupunând corectă valoarea returnatăpentru (n-1), prin înmulţirea acesteia cu n se obţine valoareacorectă a factorialului numărului natural n, valoare returnată desubprogram.

În ambele situaţii este satisfăcută condiţia de oprire.

42

Algoritmul căutării binare: un exemplu algoritm proiectat prin

aplicarea tehnicii recursivitatii si a metodei divide-et-impera:

Fie a1, a2, …, an un şir ordonat de n numere naturale (nN,

n≥2) si fie x un numar natural, dat . Se cere sa se

verifice daca numarul x se afla printre elementele sirului.

Metoda:

se injumatateste “intervalul” [[a1, an]] si se caută x în jumătatea

“cea mai apropiată” de valoarea acestuia;

urmeaza divizarea recursivă a acestei jumătăţii în alte două jumătăţi

“mai mici” şi reluarea procedeului pana la gasirea elementului sau

pana cand domeniul cautarii devine vid.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

43

LIMBAJUL C++

// bs.cpp: algoritmul recursiv de cautarebinara

int BinarySearch (float *arr, int n, float x,

int btm, int top)

{

if ( top>=btm )

{ int mid=(top+btm)/2;

if (arr[mid]==x)

return mid; //cautare cu succes

if (arr[mid]<x)

btm=mid+1;

else top=mid-1;

return BinarySearch(arr, n, x, btm, top) ;

}

else return -1; //nu s-a gasit valoareacautata

}

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Cu ajutorul acestor cazuri se va şti dacă valoarea căutată în

şir s-a găsit sau nu şi se poate returna rezultatul imediat.

Observam respectarea regulilor descrise mai sus:

1. Cazul de bază.

Undeva în funcţia recursivă, există unul sau mai multe

teste prin care se verifică conditiile de ieşire din autoapelul

recusiv. Aceste teste de ieşire se numesc cazuri de bază..

Variabilele top şi btm sunt prelucrate astfel

încât căutarea să se realizeze într-o porţiune din

ce în ce mai mică a şirului, până când unul dintre

cazurile de bază este găsit.

2. Prelucrarea progresivă. Esenţa definiţiei recursive constă în faptul că

pentru rezolvarea cazului n+1 se recurge la cazul

n. In acest fel, celelalte cazuri ale recursivităţii,

diferite de cazurile de bază, trebuie rezolvate prin

tratarea lor astfel încât procesul apelului recursiv

să le orienteze către unul dintre cazurile de bază.

44

LIMBAJUL BORLAND PASCAL

{ bs.pas: algoritmul recursiv de cautare binara }

function BinarySearch (arr:real; n: integer; x:real;

btm, top:integer) : integer;

var mid : integer;

begin

if (( top>=btm ) then

begin

mid : = (top+btm) div 2;

if (arr[mid] = x) then BinarySearch : = mid;

if (arr[mid]<x) then btm : = mid+1

else top : = mid-1;

BinarySearch:=BinarySearch(arr,n,x,btm, top)

end;

else BinarySearch : = -1;

end;

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

45

Ridicarea unui număr real x la o putere n naturală, xn binare: un

alt exemplu algoritm proiectat prin aplicarea tehnicii

recursivitatii si a metodei divide-et-impera:

Metoda clasică de ridicare la putere este multiplicarea sa cu el însuţI

de n-1 ori, iar algoritmul este de complexitate O(n).

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

46

Tehnica divide-et-impera: se poate obţine un algoritm cu complexitate:

O(log(n)).

Strategia se bazează pe următoarele proprietăţi ale puterilor întregi:

Se observă cum valorile lui n scad, până când atinge unul dintre

cazurile de bază.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

impar esten daca , x x4)par esten daca , x x3) x x2) 1 x1) 1-nn22n1 0 x

n

Cazurile care reprezintă

cazurile de bază ale recursivităţii.

Când n este par se

calculează mai întâi xn-1

şi apoi se multiplică

rezultatul cu x.

Când n este impar se

multiplică x cu el însuşi (x2)

şi apoi rezultatul se ridică

recursiv la puterea n/2.

47

LIMBAJUL BORLAND PASCAL

{pow1.pas functia putere recursiva }

function Power(x:real; n :integer): real;

begin

if (n=0) then power:=1;

if (n=1) then power:=x;

if odd ( n) then

Power:=Power(x,n-1)*x; {n impar}

Else Power:=Power(x*x, n/2); {n par}

end;

LIMBAJUL C++

//pow1.cpp functia putere recursiva

float Power(float x, int x)

{

if (n==0) return 1;

if (n==1) return x;

if (n&1)

return Power(x,n-1)*x; //n impar

else return Power(x*x, n/2); //n par

}

impar esten daca , x x4)par esten daca , x x3) x x2) 1 x1) 1-nn22n1 0 x

n

48

1. se defineşte o stivă şi se initializează cumulţimea vidă;

2. cât timp este îndeplinită condiţia decontinuare a recursivităţii:

3. se execută instrucţiunile dinainte deapel;

4. se salveaza pe stivă valorile actuale cereprezintă argumentele funcţieirecursive;

5. se execută instrucţiunile funcţieirecursive;

6. se modifică argumentele funcţieirecursive;

7. când condiţia nu mai este indeplinită şidacă stiva este nevidă atunci

8. se aduce de pe stiva un set de variabile,

9. se executa o serie de calcule (cele dedupă apelul recursiv) şi

10. se trece la pasul 3.

11. dacă stiva este vidă algoritmul se opreşte.

void print_rec()

{

int c = getch ();

if (c!=’\n’) { print_rec(); printf(“%c”,c);}

}

void print_it ()

{

Stack S;

empty (S);

int c = getch ();

while (c!=’\n’) { push(c); c = getch();}

while (nevida(S)) {c=pop (S);

printf (“%c”,c);}

}

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Pentru a tranforma o funcţie recursivă într-o funcţie iterativă:

49

Exista o legatura stransa intrerecursivitate si structurile de date de tip stiva, arbore, etc folosite in limbajele Borland Pascal si C++ pentru reprezentarea functiilor / procedurilor recursive (insasidefinitia stivelor, arborilor, listelorrealizandu-se recursiv).

Deseori, variantele iterative necesita folosirea explicita a structurii de tip stiva, generandastfel un cod extrem de laborios. In aceste situatii se considerasolutia recursiva mai eleganta, datorita simplitatii sale.

Recursivitatea trebuie inlocuitaprin iteratie atunci candrecursivitatea este prea adancasau cand limbajul de programarenu permite implementarea de apeluri recursive.

Din punctul de vedere al memorieisolicitate, o varianta recursivanecesita un spatiu de stivasuplimentar pentru fiecare apelfata de varianta iterativa.

Dimensiunea stivei trebuie aleasaastfel incat sa poata permitememorarea elementelor pentrutoate iteratiile.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

Avantajele si dezavantajele utilizarii subprogramelor recursive

50

Greseli tipice in realizarea subprogramelor recursive (1):

1. Declararea ca variabile globale a unor variabile care

controleaza adresa de revenire (cazul cand apelurile se

fac din interiorul unei structuri repetitive).

2. Declararea ca parametri transmisi prin valoare sau ca

variabile locale a unor date structurate (de exemplu de tip

tablou) micsoreaza semnificativ adancimea acceptata a

recursivitatii, deoarece memorarea lor necesita un spatiu

mare de memorie.

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

51

Greseli tipice in realizarea subprogramelor recursive (2):

4. Absenta unei conditii de oprire.

5. Exprimarea unei conditii de oprire in care nu intervin nici

variabile locale si nici parametrii transmisi prin valoare sau

prin referinta ai subprogramului.

6. Marirea dimensiunii problemei prin transmiterea in cadrul

autoapelurilor a unor parametri actuali care nu tind sa se

aproprie de valorile impuse prin conditia de oprire.

7. Neutilizarea directivei forward (limbajul Borland Pascal) in

cazul declararii unor subprograme indirect recursive

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

52

1. Algoritmi: generalitati

2. Algoritmi: modele de calculabilitate

3. Teoria functiilor recursive

4. Scheme de recurenta; reduceri

5. Recurenţă şi iteraţie in programare

BIBLIOGRAFIE1. Răzvan ANDONIE, Ilie GARBACEA: Algoritmi

fundamentali. O perspectivă C++, Editura Libris, Cluj-Napoca, 1995.

2. Cristian Sorin CALUDE: Theories of Computational Complexity, Elsevier Science Publ., Amsterdam, 1988.

3. Richard JOHNSONBAUGH, Marcus SCHAEFER: Algorithms, Pearson Prentice Hall, Upper Saddle River, NJ., 2004.

4. D. JOYCE: The Dedekind/Peano Axioms, Clark University, posted on January 2005, http://aleph0.clarku.edu/~djoyce/numbers/peano.pdf

5. Dexter C. KOZEN: Theory of Computation, Springer-Verlag, Berlin Heidelberg, 2006.