Recursivitate
Să pornim de la definiția de bază: o funcție este recursivă dacă în definiția ei se folosește o referire la ea însăși.
Din aceasta definiție putem considera modelul general al unui algoritm recursiv de forma:
rec(param_formali) { rec(param_formali) }
Pentru ca acest model să aibă sens din punct de vedere algoritmic, avem nevoie de o condiție de oprire dacă de modificările parametrilor formali:
rec(param_formali)
{
if ( conditie_iesire(param_formali) ) { instructiuni finale }
else rec(param_formali_modificati)
}
Există o serie de funcții matematice definite prin recursivitate, dintre care amintim:
> Funcția factorial
> Funcția Ackermann (Ackermann-Peter)
> Șirul lui Fibonacci
Conform definiției:
Putem interpreta definiția și în felul următor:
> Cel mai mare divizor comun (Algoritmul lui Euclid)
a) Fractali
O problemă importantă a recursivității o constituie fractalii. În această secțiune vom aminti doar sumar conceptul fractalilor geometrici în care modelul de bază al funcției recursive va genera figuri geometrice (în diferite ipostaze și diferite dimensiuni), iar condiția de oprire va fi dată de posibilitatea desenării acestor figuri geometrice (latura > 1 pixel).
Să presupunem un exemplu în care figura de bază este un pătrat (x, y, l). Procedura patrat desenează figura geometrică numită pătrat cu centrul în (x, y) și de latură l. (Fig. 1. a, b, c)
 |
| Fig. 1. a) |
Următorul subprogram:
fractal (x, y, l)
{
patrat(x, y, l);
fractal((x - l) / 2, (y - l) / 2, l / 2)
}
Va genera următoarea figură:
 |
| Fig. 1. b) |
fractal (x, y, l)
{
if ( l > 5 ) // se referă la dimensiunea în pixeli
{
patrat(x, y, l)
fractal((x - l) / 2, (y - l) / 2, l / 2)
fractal((x + l) / 2, (y + l) / 2, l / 2)
}
}
 |
| Fig. 1. c) |
În același mod se obțin și figurile clasice Koch, Sierpinski, Kepler, Cantor...
b) Turnurile din Hanoi
Nu putem vorbi de recursivitate fără să tratăm problema turnurilor din Hanoi. Această problemă presupune existența unui set de n discuri de diferite mărimi (în Fig. 2. avem n = 4 discuri), așezate în ordine pe o tijă numită sursă (discul cu circumferința cea mai mare se găsește cel mai jos). Există de asemenea încă două tije numite intermediar și destinație.
Obiectivul problemei (jocului) constă în mutarea celor n discuri de pe tija sursă pe tija destinație folosind tija intermediar cu următoarele trei restricții:
1. Se poate muta o dată o singură piesă de pe o anumită tijă (cea mai de sus). În Fig. 2. singura piesă disponibilă este cea roșie.
2. Nu se poate pune un disc de dimensiune mai mare peste un disc de dimensiune (circumferință) mai mică.
3. Numărul de mutări trebuie să fie minim.
 |
| Fig. 2. - Problema turnurilor din Hanoi |
Rezolvarea acestei probleme constă în rezolvarea a trei etape distincte.
Prima etapă necesită mutarea a n - 1 discuri de pe sursă pe intermediar, ceea ce ne va da acces la discul cel mai mare.
 |
| Fig. 3. - Prima etapă de rezolvare a problemei |
A doua etapă constă în mutarea unui disc de pe sursă pe destinație, lucru ce se poate face foarte ușor.
 |
| Fig. 4. - A doua etapă de rezolvare a problemei |
A treia etapă constă în revenirea la discurile mutate în prima etapă și să mutăm aceste n-1 discuri de pe „intermediar” pe „destinație” obținând astfel configurația finală (Fig. 5.)
 |
| Fig. 5. - A treia etapă de rezolvare a problemei |
Dacă ne uităm la restricțiile inițiale observăm că am îndeplinit doar două dintre cele trei: nu am pus un disc de dimensiune mai mare pe un disc de dimensiune mai mică și am obținut un număr minim de pași. Nu am îndeplinit însă condiția are cere să se mute un singur disc o dată (ar fi corect dacă n - 1 ar fi 1 adică n ar fi 2).
 |
| Fig. 6. - Turnurile din Hanoi cu 2 discuri |
Să revenim însă când n - 1 > 1 ca în figura 3. și să rearanjăm tijele, făcând abstracție de cel mai mare disc (nu intră în calcul decât la etapa a doua) și obținem problema turnurilor din Hanoi, dar cu n - 1 discuri și altă tijă numită intermediar (C) și altă tijă numită destinație (B).
 |
| Fig. 7. - Interschimbarea tijelor B și C |
Analog pentru etapa a treia în care se schimbă sursa și intermediarul.
 |
| Fig. 8. - Interschimbarea tijei sursă cu tija intermediar |
La acest nivel putem concepe următorul model care va constitui și baza de funcționare a algoritmului recursiv.
Funcția de rezolvare Hanoi(n, A, B, C) se poate descompune în trei subprobleme în ordinea următoare:
1. Hanoi (n - 1, A, C, B)
2. Hanoi (1, A, B, C)
3. Hanoi (n - 1, B, A, C)
Hanoi(1, A, B, C) este soluția trivială: mută de pe A pe C.
#include <iostream>
using namespace std;
using namespace std;
void Hanoi(int nDiscuri, char tSursa, char tInter, char tDest)
{
if ( nDiscuri > 0 )
{
Hanoi(nDiscuri – 1, tSursa, tDest, tInter);
cout << tSursa << " --> " << tDest << endl;
Hanoi(nDiscuri – 1, tInter, tSursa, tDest);
}
}
int main()
{
Hanoi (3,'A','B','C');
return 0;
}
Pentru a înțelege mai bine conceptul de recursivitate aplicat la acest tip de probleme, vom analiza în continuare problema turnurilor din Hanoi cu aceleași condiții inițiale, dar vom introduce încă o tijă intermediară. Pentru a obține o singură soluție la un număr dat de discuri, vom introduce restricția de a alege ca și tijă intermediară pe care să mutăm piesa curentă totdeauna cea mai din stânga liberă, în caz că sunt mai multe libere (Fig. 9.)
Fig. 9. - Turnurile din Hanoi cu 4 tije
Se poate observa deja în figura anterioară modulul de funcționare al algoritmului recursiv: Hanoi(n, A, B, C, D) înseamnă:
1. Hanoi (n – 2, A, C, D, B)
2. Hanoi (1, A, B, D, C) soluția trivială A -> C3. Hanoi (1, A, B, C, D) soluția trivială A -> D
4. Hanoi (1, C, A, B, D) soluția trivială C -> D
5. Hanoi (n – 2, B, A, C, D)
Mai trebuie să construim condiția de oprire a algoritmului recursiv. Acesta va trebui oprit fie când n ajunge la valoarea 1 fie când ajunge la 2, în funcție de valoarea inițială a lui n (par sau impar).
#include <iostream>
using namespace std;
using namespace std;
void Hanoi4tije(int nDiscuri,
char tSursa, char tInter1, char tInter2, char tDest)
{
if ( nDiscuri == 1 )
cout << tSursa << " --> " << tDest << endl;
else if ( nDiscuri == 2 )
{
cout << tSursa << " --> " << tInter1 << endl;
cout << tSursa << " --> " << tDest << endl;
cout << tInter1 << " --> " << tDest << endl;
}
else
{
Hanoi4tije(nDiscuri - 2, tSursa, tInter2, tDest, tInter1);
cout << tSursa << " --> " << tInter2 << endl;
cout << tSursa << " --> " << tDest << endl;
cout << tInter2 << " --> " << tDest << endl;
Hanoi4tije(nDiscuri - 2, tInter1, tSursa, tInter2, tDest);
}
}
int main()
{
Hanoi4tije(3, 'A', 'B', 'C', 'D');
return 0;
}
Fragmentul este luat din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.
Niciun comentariu:
Trimiteți un comentariu