Recursia
Suntem pe stradă, într-un oraş străin şi căutăm cel mai apropiat loc unde putem consulta poşta electronică.
1. V-om întreba persoanele întâlnite pe drum şi presupunând că acestea ştiu să ne răspundă apar situaţiile :
a) drumul este simplu si urmând indicaţiile, putem ajunge direct;
b) drumul este complicat, parcurgem o porţiune din drum, conform explicaţiilor primite apoi întrebăm din nou
ne confruntăm cu o nouă versiune a problemei iniţiale, dar, de data aceasta, dintr-un loc mai apropiat de destinaţia noastră.
Istorioara de mai sus rezumă esenţa repetiţiei unui anumit proces, punând în evidenţă şi pericolul ciclării acesteia
(ciclare = repetiţie infinită) - profesorul defineşte noţiunea de proces recursiv.
Expunem regulile de formare a recursiei:
- trebuie să fie formată din cazuri elementare care se rezolvă direct,
- cazuri care nu se rezolvă direct, însă procesul de calcul în mod obligatoriu progresează spre un caz elementar.
Situaţie de problemă
"Cînd un proces este recursiv? " pe baza studierii enunţului :
" Intr-o fabrică, un robot trebuie să preia piese din linia de fabricaţie şi să le aşeze pe paleţi"
- pentru a dirija activitatea de învăţare spre actul descoperirii profesorul apelează la întrebări ajutătoare:
1. După ce se umple un paiet , robotul trebuie să înceapă umplerea altuia?
2. Există mai multe procese recursive în acest caz?
3. Dacă da, care sunt acestea?
Pe baza celor enunţate înseamnă că avem de fapt două procese recursive, aflate unul în celălalt astfel spus imbricate. Un proces recursiv este acela prin care robotul trebuie să umple un paiet iar al doilea este acel că robotul trebuie să umple un număr de paleţi, aţâţi cât sunt necesari pentru a prelua piesele din fluxul de fabricaţie
Ex: - prin antiteză există şi procese recursive infinite - procesul prin care robotul preia piese din fluxul de fabricaţie şi le aşează pe paleţi ( singurele cauze care pot genera încheierea procesului fiind oprirea robotului de către factorul uman sau prin defectare).
- definiţiile recursive date în exemplu au toate aceeaşi structuгă conţinînd două părţi marcate cu (0) şi (1). - prima ramură (0) - este condiţia de oprire - execuţie pгin autoapel.
- a doua ramură (1) - descrierea operaţiilor care se fac la un pas oarecare al algoritmului (proces inductiv) - se va face analogic cu metoda inducţiei matematice.
Conceperea algoritmilor recursivi:
? Definiţi algoritmul şi scrieţi un program pentru calculului n! = 1×2×3……….n într-o manieră recursivă:
?Care este condiţia de oprire?
?Cum definim n
?Care sunt parametrii destinaţi calculului n!?
?De cîte ori se apelează funcţia ce calculează n! pentru n=3?
?Ce eroare apare la depăşirea limitei superioare a stivei?
Răspuns:
! Se înmulţesc toate numerele de la 1 la n.
!Din definiţie avem că 0! = 1
!Toate cazurile se reduc la cazul elementar 0! (n-1, n-2 … )
Exemplul programului:
Program factorial;
Var n:byte;
Function Fact(n:byte):longint;
Var f:longint;
Begin
Write('apel pentru n=',n);
If n=0 then f:=1
Else f:=n*fact(n-1);
Fact:=f;
Writeln('Revenire din apelul pentru n=',n,', ',n,'!=',f)
End;
Begin
Write('n='); Readln(n);
Fact(n);
End.
Var n:byte;
Function Fact(n:byte):longint;
Var f:longint;
Begin
Write('apel pentru n=',n);
If n=0 then f:=1
Else f:=n*fact(n-1);
Fact:=f;
Writeln('Revenire din apelul pentru n=',n,', ',n,'!=',f)
End;
Begin
Write('n='); Readln(n);
Fact(n);
End.
 |
| Pe diagrama respectivă se explică lucrul recursiei şi se face analogie cu iteraţia. |
Recursia se defineşte ca o situaţie, în care un subprogram se autoapelează, fie direct, fie prin intermediul altei funcţii sau proceduri. Subprogramul care se autoapelează se numeşte recursiv.
1. Numerele naturale:
a) 1 este număr natural;
b) Numărul întreg ce urmează imediat după un număr natural este un număr natural.
2. Funcţia factorial(n) pentru numere întregi nenegative:
a) factorial(0)=1,
b) factorial(n)=n*factorial(n-1), dacă n>1.
Recursia este utilă pentru programarea unor calcule repetitive. Repetiţia este asigurată prin execuţia unui subprogram, care conţine un apel la el însuşi: cînd execuţia ajunge la acest apel, este declanşată o nouă execuţie ş.a.m.d.
Orice subprogram recursiv trebuie să includă condiţii de oprire a procesului repetitiv.
La orice apel de subprogram în memoria calculatorului vor fi depuse următoarele informaţii:
· Valorile curente ale parametrilor transmişi prin valoare;
· Locaţiile (adresele) parametrilor – variabilă;
· Adresa de retur, adică adresa instrucţiunii ce urmează după apel.
