Recursivitate

11

Click here to load reader

Transcript of Recursivitate

Page 1: Recursivitate

MATERIAL DIDACTIC PENTRU STUDENŢILA DISCIPLINA “BAZELE PROGRAMĂRII”

RECURSIVITATE

Elaborat: Bacalîm Alinastudentă la USB “Alecu Russo”

10.01.2011 desktop:recursie.ppt

Page 2: Recursivitate

Recursivitatea reprezintă o tehnică de programare de o importanţă deosebită. Ea permite o exprimare extrem de concisă şi clară a algoritmilor de rezolvare a unor probleme complexe.

În matematică, o noţiune este definită recursiv dacă în cadrul definiţiei apare noţiunea care se defineşte.

Page 3: Recursivitate

Definiţia recursivă a factorialului unui număr natural n este:

1, dacă n=0n! = n*(n-1)!, dacă n>0

Exemplu:5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 120

Page 4: Recursivitate

În programare, recursivitatea se exprimă cu ajutorul subprogramelor, deoarece ele se identifică printr-un nume care este apoi specificat apoi în apeluri.

Un subprogram este recursiv dacă se autoapelează.

Page 5: Recursivitate

Dacă apelul subprogramului apare chiar în corpul său, recursivitatea se numeşte directă. Iar dacă apelul subprogramului recursiv apare în corpul unui alt subprogram care se apelează direct sau indirect din subprogramul recursiv, recursivitatea se numeşte indirectă.

Page 6: Recursivitate

Un subprogram este activ de la apelul său până la revinirea în subprogramul apelant. Subprogramul rămîne activ, chiar dacă din cadrul său se activează alte subprograme. Astfel, se poate spune, că un subprogram este recursiv dacă apelul său apare când subprogramul este activ.

Page 7: Recursivitate

Executarea unei proceduri nerecursive P1 care apelează o altă procedură nerecursivă P2 constă în:- executarea secvenţei de început a procedurii P1 care precede apelul procedurii P2;- executarea procedurii P2:- executarea secvenţei de sfârşit a procedurii P1.

Page 8: Recursivitate

Schema generală a unei proceduri recursive:

Page 9: Recursivitate

Procedure P1VarX: CharBeginReadChar(X)If X <> ‘.’ Then

P1EndWriteChar(X)EndBeginP1END.

Exemplu rezolvat

Page 10: Recursivitate

Fie ca de la tastatura se introduce sirul 1a2. , atunci se vor crea urmatoarele cadre:

La ecran va fi afişat 2a1

Page 11: Recursivitate

SFÎRŞIT