Recursivitate

Recursivitatea este acel mecanism prin care un modul (functie, procedura) se autoapeleaza.

Recursivitatea este utilizata cu precadere in situatiile in care trebuie implementata o functie recursiva, adica o functie definita prin ea insasi la un alt nivel. Este un mecanism introdus recent datorita simplitatii sale.

I.1          Clasificarea definitiilor recursive

In functie de modul in care o definitie (functie) se autoapeleaza, avem urmatoarele tipuri de recursii:

I.      recursie directa: are loc atunci cand o functie se autoapeleaza pe ea insasi. Exista mai multe forme de autoapelari:

I.1.           recursie liniara: este intalnita in cazul in care evaluarea functiei intr-un punct presupune evaluarea unei alte valori a functiei. Functiile recursive liniare se dezvolta pe un singur nivel.

De exemplu, varianta recursiva a factorialului, unde:

Evaluarea termenului f(3), presupune evaluarea termenului f(2), care la randul sau va evalua pe f(1) samd. pana cand succesiunea de reapelari se opreste, n fiind 0. Altfel spus,

f(3)=3*f(2)=3*2*f(1)=3*2*1*f(0)= 3*2*1*1=6.

Succesiunea de autoapelari este liniara: f(3) ← f(2) ← f(1) ← f(0), de unde si denumirea de recursie liniara.

I.2.    recursie neliniara, care la randul ei poate avea mai multe forme:

I.2.1.        recursie in cascada: evaluarea functiei intr-un punct necesita evaluarea mai multor valori ale functiei.

De exemplu, sirul lui Fibonacci descris prin functia de mai jos:

Sirul lui Fibonacci este un exemplu de recursie in cascada deoarece evaluarea celui de-al n-lea termen Fib(n) comporta evaluarea celor doi termeni imediat anteriori: Fib(n-1) si Fib(n-2).

Reprezentarea arborescenta a modului in care este evaluat un anumit termen sugereaza o cascada, de unde si denumirea metodei. O abordare recursiva a problemei va duce la completarea arborelui in maniera top-down.

Fig. II . Recursivitate in cascada

I.2.2.        recursie de tip impachetat: evaluarea functiei intr-un punct presupune evaluari repetate, imbricate ale functiei in alte puncte.

De exemplu, functia Manna-Pnueli M(x), de forma:

Un alt exemplu de functie recursiva de tip impachetat este functia lui Ackermann, , definita mai jos:

Recursia neliniara (in cascada sau de tip impachetat) duce adeseori la recalculare de termeni: se observa imediat in figura II.1. ca in procesul de evaluare a lui Fib(n-1) se ajunge la evaluarea lui Fib(n-2), care va fi apoi reevaluat la nivelul lui Fib(n). Recalcularea unor valori ale functiei face ca implementarea recursiva sa fie ineficienta ducand la timpi indelungati de calcul chiar si pentru valori moderate ale lui n. In aceasta situatie se recomanda metode alternative asa cum vom vedea mai departe in cadrul acestei sectiuni.

II.      recursie indirecta, are loc atunci cand o functie se autoapeleaza (indirect)    apeland o alta functie, care la randul sau o apeleaza pe prima. De exemplu, sirurile:

I.2          Mecanismul de functionare

In scopul realizarii unui algoritm recursiv, trebuie sa se aiba in vedere urmatoarele doua principii:

la orice nivel de executie se intampla acelasi lucru, asa ca este suficient sa ne imaginam ce se intampla la un singur nivel;

algoritmul va contine si o ramura direct calculabila (care nu se defineste prin ea insasi), parte care va asigura iesirea din nivelul curent de recursivitate. In caz contrar, executia functiei recursive se va incheia in mod fortat, odata cu umplerea stivei, nerespectand principiul finititudinii algoritmilor. De exemplu, in cazul variantei recursive a factorialului, valoarea direct calculabila este obtinuta pentru n=0 si este 1, evaluarea ei nu necesita un reapel.

La fiecare reapel al functiei recursive, compilatorul rezerva spatiu pe stiva pentru a incarca parametrii formali, variabilele automatice ale functiei si adresa zonei de revenire unde s-a realizat reapelul. Fiecarui reapel al functiei ii va fi rezervat un alt segment pe stiva, ceea ce face ca valorile variabilelor sa poata fi diferite. La revenirea dintr-un apel recursiv, segmentul corespunzator al stivei este eliberat si se revine in functia apelanta in punctul imediat urmator apelului recursiv. Subliniem faptul ca gestiunea stivei este sarcina exclusiva a compilatorului.

Trebuie retinut ca o definitie recursiva trebuie sa satisfaca conditia de consistenta, prin care valoarea functiei intr-un punct este fie direct calculabila, fie calculabila prin intermediul unor alte valori, in caz contrar se va ajunge, asa cum am spus mai sus, la umplerea stivei si incheierea fortata a programului. O functie care nu contine ramura direct calculabila nu satisface conditia de consistenta. Similar, functia definita mai jos:

nu satisface conditia de consistenta pentru argumente pozitive.

In continuare sa consideram exemplul functiei factorial:

In limbajul C++, functia recursiva va fi:

double factR(int n)

Sa urmarim evolutia stivei atunci cand functia factR este apelata pentru n=2.

Se aloca pe stiva un segment in care se incarca parametrul n cu valoarea de la apel (2) si adresa de revenire in functia apelanta. Se executa functia. Intrucat n nu este 0, se executa a doua linie, care presupune un reapel al functiei factR, pentru n=1.

rev=adresa 2 n=1 rev=adresa 1 n=2	Se reapeleaza factR, cu n=1. Se aloca pe stiva parametrul n cu valoarea 1 si adresa de revenire in functia factR (la apelul anterior), adresa2. Intrucat n nu este 0, se reapeleza din nou factR, pentru n mai mic cu o unitate: n=0.
rev=adresa 3 n=0 rev=adresa 2 n=1 rev=adresa 1 n=2	Se reapeleaza factR, cu parametrul n=0. Se aloca pe stiva un nou segment, unde sunt incarcati parametrul n, cu valoarea 0 si adresa de revenire: adresa3. De aceasta data, pentru ca n este nul, se va executa prima linie de cod, care asigura revenirea in recursivitate, cu o valoare direct calculabila: valoarea 1. Odata ce s-a executat instructiunea return 1, care determina incheierea executiei (apelului curent al) functiei, segmentul de stiva corespunzator este sters si se revine in punctul imediat urmator apelului anterior, la adresa adresa1.
rev=adresa 2 n=1 rev=adresa 1 n=2	In acest moment valoarea curenta a variabilei n este 1, deci se va evalua expresia 1*1 si se va returna apelului anterior valoarea 1, in punctul adresa2, dupa ce va sterge segmentul corespunzator de stiva.
rev=adresa 1 n=2	Acum valoarea variabilei n este 1, ceea ce va determina returnarea apelului anterior a valorii 2*1, in punctul adresa1, care corespunde functiei principale. In acest moment stiva este complet distrusa.

Trebuie subliniat faptul ca variabilele statice (declarate in interiorul functiei) sunt alocate intr-o zona speciala de memorie, nu pe stiva si, prin urmare nu au acelasi comportament ca variabilele automatice, ele pastrandu-si intotdeauna ultima valoare, inclusiv la revenirea din apel. Ca exercitiu, lasam cititorul sa imagineze evolutia stivei functiei recursive de mai jos, care are acelasi efect ca si cea studiata:

double factR2(int n)

Unele tehnici de programare (cum a fi Divide et Impera) sau metode de cautare, sortare au la baza principiul recursivitatii.

I.3          Iterativitate sau recursivitate

Un algoritm iterativ accepta intotdeauna o rezolvare recursiva, la fel si invers. Prin urmare, alegerea metodei de rezolvare ramane in sarcina programatorului. El trebuie sa tina cont de complexitatea algoritmului realizat si, nu in ultimul rand, de efortul de programare. Implementarile recursive presupun un cod sursa mai scurt, ele constand, in cea mai mare parte a cazurilor, in transcrierea unei definitii matematice recursive intr-un limbaj de programare. In anumite situatii, insa, ele conduc la timpi de calcul indelungati si un consum sporit de memorie (determinat de utilizarea stivei), situatii in care rezolvarile iterative sunt preferabile

Sa consideram din nou exemplul functiei lui Fibonacci.

,

Definitia recursiva a acestei functii face ca implementarea recursiva sa fie imediata:

Recalcularea termenilor face ca implementarii recursiva sa i se asocieze o complexitate de ordin exponential. Intr-adevar, daca T(n) este numarul de autoapelari ale functiei necesar evaluarii termenului n, atunci:

Prin inductie matematica se poate arata imediat ca :

Relatia se verifica pentru n=2 si n=3 si

asadar, varianta recursiva este de complexitate exponentiala .

Evident, un algoritm mai eficient ar evita recalcularea termenilor. In cazul functiei lui Fibonacci, o solutie alternativa ar fi realizarea unei implementari iterative:

Solutia iterativa corespunde unei incarcari a arborelui asociat problemei in maniera bottom-up.

In multe probleme reale realizarea unei implementari iterative pentru o definitie recursiva nu este atat de imediata. Atunci se recurge la metoda tabelarii, asa cum vom vedea mai jos.

I.4          Metoda tabelarii

Metoda tabelarii este utilizata ca metoda alternativa atunci cand implementarea unei definitii recursive duce la recalcularea unor termeni. Ideea este de a folosi o tabela de date (un masiv suplimentar) in care sa fie memorate valorile functiei odata ce au fost calculate. Dimensiunea masivului (unidimensional, bidimensional samd.) este data de paritatea functiei. Strategia de lucru este urmatoarea:

Scopul memorarii valorilor deja calculate este acela de a reduce complexitatea algoritmului.

In cazul functiei Fibonacci se    vor retine intr-un vector cu n+1 componente valorile functiei, pe masura ce sunt calculate.

In programul principal se va initializa vectorul cu 0, exceptand primele doua elemente care vor fi 1.

Prin metoda tabelarii s-a obtinut un algoritm recursiv de complexitate O(n) in care pe masura ce numarul de termeni evaluati creste, creste si numarul de valori direct calculabile ale definitiei recursive, acestea fiind termenii nenuli din tabela. Din acest motiv, in unele lucrari de specialitate metoda tabelarii este privita ca o metoda de programare dinamica.

Avantajul tabelarii valorilor deja calculate este evident: un algoritm de ordin exponential a fost transformat intr-unul liniar; memoria suplimentara utilizata (tabela de valori) este acceptabila.

Ideea de a retine valorile calculate intr-o tabela poate fi exploatata si altfel; in cazul functiei Fibonacci putem utiliza algoritmul:

Si aceasta abordare are ca efect completarea arborelui de valori ale functiei tot in maniera bottom-up.

I.5          Aplicatii

I.5.1         Procedura pentru factorial recursiv

Sa se realizeze o procedura (nu functie!) recursiva care calculeaza n!, pentru un n dat.

Solutie:

In limbajul C/C++ a fost creata o functie care nu intoarce valoare:

Procedura pentru factorial recursiv

#include<iostream.h>

void fact(int n, double &f)

void main()

I.5.2         Inversarea sirului de caractere

Folosind stiva creata prin recursivitate, sa se inverseze caracterele unui sir introdus la tastatura.

Solutie:

Inversarea sirului de caractere

#include<conio.h>

#include<stdio.h>

void Inversare()

main()

Incercati textul "Ion a luat luni vinul tau la noi". Functioneaza algoritmul?

I.5.3         Siruri - Recursivitate indirecta

Sa se exemplifice modul de utilizare a recursivitatii indirecte, generand valorile sirurilor a_n si b_n, definite mai jos, pentru a, b si n introduse la tastatura:

Solutie:

Siruri-Recursivitate indirecta

#include<iostream.h>

#include<math.h>

double A(int, double, double);

double B(int, double, double);

double A(int n, double a, double b)

double B(int n, double a, double b)

main()

I.5.4         Algoritmul lui Euclid

Sa se implementeze, iterativ si recursiv, algoritmul lui Euclid pentru determinarea cmmdc a doua numere intregi nenule. Sa se utilizeze una dintre variante pentru a determina cmmdc a unui sir de numere intregi nenule.

Indicatie:

Algoritmul lui Euclid: fie a si b cele doua numere intregi pozitive.

Solutie:

Algoritmul lui Euclid pentru cmmdc

#include<iostream.h>

int cmMdcI(int a, int b)

return a;

int cmMdcR(int a, int b)

main()

while(a);

cout<<'cmMdc al sirului este '<<cmMdc;

return 0;

Observatie:

S-a utilizat procedeul reprezentat mai jos:

Fig. II . Determinarea cmmdc al unei liste de numere intregi

Pentru determinarea cmmdc al sirului de numere, variabila cmmdc a fost initializata cu 0, pentru ca ea sa devina primul numar din sir, dupa prima iteratie a instructiunii dowhile. S-a tinut cont de faptul ca, in algoritmul lui Euclid, daca un numar (parametru al functiilor cmMdcI sau cmMdcR) este nul, cmmdc va fi celalalt numar.

Cel mai mic multiplu comun a doua numere intregi se poate deduce folosind relatia:

a*b=cmMmc(a, b)*cmmmc(a, b)

I.5.5         Triunghiul lui Pascal

Sa se calculeze coeficientii binomiali C_n^k, pentru n<N (N dat) si in varianta recursiva si sa se utilizeze pentru a afisa Triunghiul lui Pascal.

Celebrul triunghi poarta numele matematicianului francez Blaise Pascal pentru ca a fost prezentat in tratatul acestuia "Traite du Triangle Arithmetique", aparut in anul 1653. Cu toate acestea, coeficientii binomiali au o istorie mult mai indelungata: ei apar mai intai in scrierile grecesti si latine in interpretare geometrica pentru valori mici ale lui n si k. O prezentare detaliata a lor apare in jurul anului 1150 intr-o lucrare hindusa. Triunghiul "lui Pascal" a aparut si el cu mult inaintea vremii celui al carui nume il poarta si anume in sec. XIV, in lucrarea "Pretioasa oglinda a celor patru elemente" apartinand unui matematician chinez.

Indicatie:

Formula de calcul este:

sau in varianta recursiva:

Pentru ca implementarea recursiva a functiei de mai sus duce la recalculare de termeni, se va utiliza metoda tabelarii. Fiecare valoare C_n^k, odata calculata, va fi retinuta in componenta Table[n][k]; astfel, masivul Table va fi bidimensional cu N linii, fiecare linie n avand n+1 componente (masivul va fi incarcat numai pe jumatate: ).

Solutie:

Triunghiul lui Pascal

#include <iostream.h>

int C(int n,int k,int**Table)

main()

}

for(n=0;n<N;n++)

delete[]Table[n];

delete[]Table;

return 0;

Pentru N=7, aplicatia va afisa:

Asa cum rezulta din formula recursiva de calcul, fiecare element din mijloc este egal cu suma dintre cel de deasupra sa si cel din stanga acestuia.

I.5.6         Problema crescatorului de iepuri

Un taran isi propune sa cumpere o pereche de iepuri tineri. Presupunand ca o pereche de iepuri se inmulteste odata in fiecare luna si are un singur pui care devine fertil dupa o luna, in plus, iepurii nu mor, cate perechi de iepuri va avea taranul dupa un an?

Asadar, la inceput taranul are o singura pereche de iepuri, in luna a doua perechea devine fertila si se inmulteste, astfel ca la inceputul lunii a treia taranul va avea doua perechi de iepuri, in a patra luna va avea trei perechi (perechea de o luna inca nu s-a inmultit), in cea de-a 5-a luna vor fi 5 perechi samd.

Aceasta problema a fost imaginata in sec. XIII, de catre cel mai mare matematician european al evului mediu, italianul Leonardo Fibonacci (fiul lui Bonaccio), referit si ca Leonardo Pisano (Leonardo din Pisa), si publicata in lucrarea sa Liber Abaci - Cartea Abacului, ca o introducere a celebrului sir de numere care ii poarta numele: 1, 1, 2, 3, 5, 8, 13, 21, 34 in care un termen este suma celor doi imediat anteriori. Proprietatile deosebite ale acestor numere au facut ca ele sa fie obiectul de interes al invatatilor tuturor timpurilor, astfel ca sirul fusese descris cu mult inainte de savanti indieni, interesati de tiparele muzicale ritmice formate ca succesiuni de batai simple sau duble.

Sirul lui Fibonacci are aplicatii deosebite, in primul rand datorita frecventelor sale observari in natura. Si pentru programatori sirul lui Fibonacci este important. O prima aplicare practica a sa a avut loc in 1837 cand E. Leger a reusit sa evalueze complexitatea algoritmului lui Euclid, observand ca pentru valori ale numerelor a si b mai mici decat un termen F_k, algoritmul itereaza de cel mult k+1 ori.

Practic, problema crescatorului de iepuri se rezuma la a determina un termen din sirul lui Fibonacci. Astfel, dupa un an de zile, crescatorul va avea un numar de iepuri egal cu cel de-al 13-lea termen din sirul lui Fibonacci, F₁₂₊₁=F₁₃=233 de perechi de iepuri. Sa se construiasca mai multe variante de rezolvare -iterative si recursive- si sa se compare.

Solutie:

Generarea termenilor sirului lui Fibonacci

#include<iostream.h>

typedef unsigned long INT;

INT *Table;

INT FibR(int n)

INT FibI(int n)

return Fib2;

INT FibRT(int n)

INT FibIT(int n)

main()

Observatie: Desi implementarea recursiva necesita un efort minim de programare, ea conduce la o recursie in cascada, de aceea variantele alternative sunt mult mai eficiente. Testati separat cele patru versiuni pentru n=25. Apoi incercati n=50. Ce observati? Evaluati complexitatea celor patru variante si comparati-le.

I.5.7         Functia lui Ackermann

Sa se genereze valoarea functiei lui Ackermann, intr-un punct dat.

Solutie:

Functia lui Ackermann

#include<iostream.h>

long Ack(int m, int n)

main()

Ex: Ack(3,2)=29.

Observatie: Volumul mare de memorie necesar implementarii recursive a problemei, chiar si pentru valori mici ale parametrilor, face ca functia lui Ackermann sa fie utilizata pentru testarea performantelor compilatoarelor.

I.5.8         Comparare alfanumerica siruri

Sa se realizeze o functie care compara alfanumeric (similar cartii de telefon) doua siruri de caractere. Functia va returna 1 daca primul sir este mai mare decat al doilea, 0 daca sunt egale si -1 daca cel de-al doilea sir este mai mare.

Indicatie: Se vor compara primele caractere din cele doua siruri. Daca difera (chiar daca un sir s-a terminat si celalalt nu), atunci se poate lua o decizie. Daca sunt egale se trece la compararea caracterelor de pe pozitia urmatoare.

Solutie:

Comparare alfanumerica

#include<iostream.h>

int strcmp(char *a, char *b)

main()

cout<<a<<rez<<b;

return 0;

Exemplu: Popescu<Popovici, Pop=Pop, popescu>Popovici, Pop<Popovici

Observatie: In programul de mai sus s-a tinut cont de faptul ca terminatorul de sir (caracterul '0') are codul ASCII 0, fiind astfel mai mic decat orice alt caracter fara semn.

I.5.9         Suma puterilor

Daca sisunt solutiile ecuatiei de gradul II: cu coeficienti reali, sa se calculeze suma pentru un n numar natural dat.

Indicatie

Se va incerca gasirea unei formule recursive pentru suma ceruta. Astfel, daca sisunt solutiile ecuatiei, atunci ele o verifica:

.

Inmultind prima relatie cu si pe a doua cu :

obtinem ca:    .

Adunand cele doua relatii si punand , obtinem relatia de recurenta dorita:

.

De aici incolo scrierea unei functii recursive este imediata.

Solutie:

Suma puterilor radacinilor

#include<iostream.h>

double S=4.,P=4.;

double Suma(int n)

main()

Se observa ca algoritmul prezentat duce la recursie in cascada cu recalculare de termeni, de aceea este indicata realizarea unei variante alternative.

I.5.10     Ridicarea la putere - Optimizarea recursivitatii

Sa se realizeze functii, in doua variante, una iterativa si alta recursiva. pentru ridicarea la putere (intreaga) a unui numar oarecare.

Indicatie: Cazul in care n este negativ se reduce imediat la situatia cu exponent pozitiv: .

Solutie:

Ridicare la putere

#include<iostream.h>

#include<math.h>

double PowR(double x, int n)

double PowI(double x, int n)

main()

Cele doua variante, iterativa si recursiva, sunt similare din punctul de vedere al timpului de executie, exprimat prin numarul de inmultiri efectuate: pentru n pozitiv avem n inmultiri in ambele situatii. In varianta recursiva este utilizata stiva, rezulta ca pentru valori foarte mari ale lui n se poate produce depasirea memoriei.

Varianta recursiva este un exemplu de utilizare a metodei de programare Divide et Impera, in care rezolvarea unei probleme de dimensiune n a fost redusa la rezolvarea unei sub-probleme de dimensiune n-1. Solutia de programare poate fi imbunatatita simtitor daca sub-problema la care reducem va fi de dimensiune n/2.    Pentru n este pozitiv vom considera utiliza relatia:

Prin [n/2] am inteles partea intreaga a impartirii (care in limbajul C se scrie simplu, n/2, avand in vedere ca cei doi operanzi sunt numere intregi), iar prin n%2 restul impartirii lui n la 2.

In aceasta varianta, stiva va avea k niveluri, atunci cand . Asadar, numarul de niveluri , este imbunatatit simtitor fata de varianta anterioara, cu n niveluri ale stivei.

Ridicare optimizata la putere

double PowR2(double x, int n)