Functii recursive

O definiţie recursivă foloseşte termenul de definit în corpul definiţiei. O funcţie poate fi recursivă, adică se poate apela pe ea însăşi, în mod direct sau indirect, printr-un lanţ de apeluri.

/* apel recursiv direct */
void f(int x) {
. . .
f(10);
. . .
}

/* apel recursiv indirect */
void f1(int x) { 
. . . . . .
f2(10); 
. . . . . .
}
void f2(int y) {
f1(20);
}

În cazul recursivităţii indirecte, compilatorul trebuie să verifice corectitudinea apelurilor recursive din fiecare funcţie. O declarare anticipată a prototipurilor funcţiilor oferă informaţii suficiente compilatorului pentru a face verificările cerute.

Funcţiile definite recursiv sunt simple şi elegante. Corectitudinea lor poate fi uşor verificată.

Definirea unor funcţii recursive conduce la ineficienţă, motiv pentru care se evită, putând fi înlocuită întotdeauna prin iteraţie.

Definirea unor funcţii recursive este justificată dacă se lucrează cu structuri de date definite tot recursiv

Exemple de definiţii recursive: Multe obiecte matematice au definiri recursive, care pot fi exploatate algoritmic. De exemplu:

/* Factorialul unui numar */
int fact_iterativ(int n) {
    int p = 1;
    for(int i = 1 ; i <= n ; i ++)
        p = p * i;
    return p;
}

int fact_recursiv(int n) {
    if(n == 0)
        return 1;
    else
        return n * fact_recursiv(n-1);
}

/* Calculat cel mai mare divizor comun */
int cmmdc(int a, int b) {
    if (a == b)
        return a;
    else
        return cmmdc(b, a % b);
}

Recursivitate liniară: Este forma cea mai simplă de recursivitate şi constă dintr-un singur apel recursiv. De exemplu pentru calculul factorialului avem:

• f(0)=1 cazul de bază
• f(n)=n*f(n-1) cazul general

Complexitatea in acest caz este liniară O(n), ca la algoritmul iterativ, însă ne consumă foarte multă stivă.

Recursivitatea binară presupune existenţa a două apeluri recursive. Exemplul tipic îl constituie şirul lui Fibonacci:

long fibo(int n) {
    if(n<=2) 
        return 1;
    return fibo(n-1) + fibo(n-2);
}

Funcţia este foarte ineficientă, având complexitate exponenţială, cu multe apeluri recursive repetate. O implementare iterativă ar fi:

unsigned long fib_iter(int n) {
    // program simplu si eficient (complexitate liniara)
    unsigned long a=1, b=1, c;
    int k;
    
    for(k=2; k<=n; k++){
        c = a + b;
        a = b;
        b = c;
    }

    return b; //functioneaza corect si pt. n=0 sau n=1
}
// observatii: la n=40 varianta recursiva dureaza foarte mult
// la n=45 varianta iterativa da inca rezultat corect
// pentru n>45 executia iterativa este rapida dar rezultatul depaseste unsigned long

Se poate înlocui dublul apel recursiv printr-un singur apel recursiv. Pentru aceasta ţinem seama că dacă a, b şi c sunt primii 3 termeni din şirul Fibonacci, atunci calculul termenul situat la distanţia n în raport cu a, este situat la distanţa n-1 faţă de termenul următor b. Necesitatea cunoaşterii termenului următor impune prezenţa a doi termeni în lista de parametri. Algoritmul rezultat are complexitate liniară.

long f(long a, long b, int n){
    if(n<=1)
        return b;
    return f(b, a+b, n-1);
}


long fiblin(int n){
    f(0, 1, n);
}

Un algoritm recursiv obţine soluţia problemei prin rezolvarea unor instanţe mai mici ale aceleeaşi probleme.

• se împarte problema în subprobleme de aceeaşi natură, dar de dimensiune mai scăzută
• se rezolvă subproblemele obţinându-se soluţiile acestora
• se combină soluţiile subproblemelor obţinându-se soluţia problemei
• ultima etapă poate lipsi (în anumite cazuri), soluţia problemei rezultând direct din soluţiile subproblemelor.
• procesul de divizare continuă şi pentru subprobleme, până când se ajunge la o dimensiune suficient de redusă a problemei care să permită rezolvarea printr-o metodă directă.
• metoda divizării se exprimă natural în mod recursiv: rezolvarea problemei constă în rezolvarea unor instanţe ale problemei de dimensiuni mai reduse

Exemple de rezolvare de probleme simple

Ridicarea unui număr la o putere întreagă.

double putere(double x, int n) {
    if (n==0) 
        return 1;
    double y = putere(x, n/2);
    if (n%2==0)
        return y*y;
    else
        return x*y*y;
}

Căutarea binară presupune căutarea unei valori într-un tablou sortat. În acest scop

• se compară valoarea căutată y cu elementul din mijlocul tabloului x[m]
• dacă sunt egale, elementul y a fost găsit în poziţia m
• în caz contrar se continuă căutarea într-una din jumătăţile tabloului (în prima jumătate, dacă y<x[m] sau în a doua jumătate dacă y>x[m]).
• Funcţia întoarce poziţia m a valorii y în x sau -1, dacă y nu se află în x. Complexitatea este O(log n)

int CB(int i, int j, double y, double x[]) {
    double m = (i+j)/2;

    if(i > j)
        return -1;
    if(y == x[m])
        return m;

    if(y < x[m])
        return CB(i, m-1, y, x);
    else
        return CB(m+1, j, y, x);
}


int CautBin(int n, double x[], double y) {
    if(n==0)
        return -1;
    return CB(0, n-1, y, x);
}

Localizarea unei rădăcini a ecuaţiei f(x)=0, separată într-un interval [a, b] prin bisecţie este un caz particular de căutare binară. Deoarece se lucrează cu valori reale, comparaţia de egalitate se evită.

double Bis(double a, double b, double (*f)(double)){
    double c = (a+b)/2;
    const double EPS = 0.01;

    if(fabs(f(c)) < EPS || b-a < EPS) return c;
    if(f(a)*f(c) < 0)
        return Bis(a, c, f);
    else
        return Bis(c, b, f);
}

Elementul maxim dintr-un vector: Aplicarea metodei divizării se bazează pe observaţia că maximul este cea mai mare valoare dintre maximele din cele două jumătăţi ale tabloului.

double max(int i, int j, double *x) {
    double m1, m2;
    if(i==j)
        return x[i];
    if(i==j-1) 
        return (x[i] > x[j] ? x[i] : x[j]);

    int k = (i+j)/2;
    m1 = max(i, k, x);
    m2 = max(k+1, j, x);
    return (m1 > m2) ? m1 : m2;
}

Turnurile din Hanoi (link pbinfo) Se dau 3 tije: stânga, centru, dreapta; pe cea din stânga sunt plasate n discuri cu diametre descrescătoare, formând un turn. Generaţi mutările care deplasează turnul de pe tija din stânga pe cea din dreapta. Se impun următoarele restricţii:

• la un moment dat se poate muta un singur disc
• nu se permite plasarea unui disc de diametru mai mare peste unul cu diametrul mai mic
• una din tije serveşte ca zonă de manevră.6 Problema mutării celor n discuri din zona sursă în zona destinaţie poate fi redusă la două subprobleme:
• mutarea a n-1 discuri din zona sursă în zona de manevră, folosind zona destinaţie ca zonă de manevră
• mutarea a n-1 discuri din zona de manevră în zona destinaţie, folosind zona sursă ca zonă de manevră
• Între cele două subprobleme se mută discul rămas în zona sursă în zona destinaţie

#include <iostream>
using namespace std;

// Turnurile din Hanoi - mutarile pentru deplasarea a n discuri
// de pe tija din stanga pe cea din dreapta, folosind tija din
// mijloc ca zona de manevra
void hanoi(int n, int sursa, int man, int dest);

int main() {
    int n;
    cin >> n;
    hanoi(n, 1, 2, 3);
    return 0;
}

void hanoi(int n, int sursa, int man, int dest) {
    if(n){
        hanoi(n-1, sursa, dest, man);
        cout << sursa << "->" << dest << endl;
        hanoi(n-1, man, sursa, dest);
    }
}

Extragerea cifrelor unui număr

#include<iostream>
using namespace std;
 
void extract(int n) {

    if(n == 0)
        return;
 
    extract(n / 10);
    cout << n % 10 << endl; 
}
 
int main()
{
    // A se observa ca acest mod de scriere va afisa exact 1,2,3,4 nu 4,3,2,1
    extract(1234);
    return 0;
}

Rezolvare problema FCrescRec de pe pbinfo:

// Scrieți funcția recursivă FCrescRec care primind ca parametru un număr natural n, 
// returnează 1 dacă cifrele sale, începând cu cifra unităţilor sunt dispuse în ordine 
// crescătoare, sau returnează 0 dacă n nu are cifrele în ordine crescătoare.

int FCrescRec(int n) {

    //Caz de baza: cifra - le consider sortate
    if (n < 10)
        return 1;

    int dr = n % 10; // cifra din dreapta
    n = n / 10;
    int dl = n % 10; // a doua cifra dupa cea din dreapta
    int curr = dl > dr ? 1 : 0; // se compara cele doua cifre
    if (dl == dr) curr = 1; // daca sunt egale - le consider sortate

    // Am ajuns la cifra -> returnez rezultatul curent
    if (n < 10)
        return curr;

    return curr == FCrescRec(n) ? curr : 0; // se continua comparatiile
}

Rezolvare problema CifDiv3rec de pe pbinfo:

int CifDiv3Rec(int n) {
    // Caz de baza -> o singura cifra
    if (n < 10) {
        if (n % 3 == 0)
            return 1;
        else
            return 0;
    }

    // Cazul "curent"
    int c = n % 10;
    if (c % 3 == 0)
        return 1 + CifDiv3Rec(n / 10); //adun 1 c-am gasit cifra curenta divizibila cu 3
    else
        return CifDiv3Rec(n / 10); //nu adun nimic
}