Functii recursive

Introducere

Recursivitatea reprezintă proprietatea unor noțiuni de a se defini prin ele însele.
Exemple:
-factorialul unui număr: N!=N⋅(N−1)! ;
-ridicarea la putere: a^n=a⋅a^n−1 ;
-termenul unei progresii aritmetice: an=an−1+r ;
-șirul lui Fibonacci: Fn=Fn−1+Fn−2 ;
Să observăm că aceste reguli nu se aplică întotdeauna. Dacă ar fi așa, pentru 3! am obține: 3!=3⋅2! , 2!=2⋅1! , 1!=1⋅0! , 0!=0⋅(−1)! De aici am putea deduce că 0!=0 și înlocuind în relațiile de mai sus obținem că n!=0 , pentru orice număr natural n . Bineînțeles, nu este corect. De fapt, formula recursivă pentru n! se aplică numai pentru n>0 , iar prin definiție 0!=1 .
Astfel, identificăm următoarea definiție pentru n! , acum completă: n!={1n⋅(n−1)!dacă n=0,dacă n>0. Similar, pentru toate formulele de mai sus exista cel puțin o situație în care formula recursivă nu se mai poate aplica, iar rezultatul se determină în mod direct. În C++, recursivitatea se realizează prin intermediul funcțiilor, care se pot autoapela. Ne amintim că o funcție trebuie definită iar apoi se poate apela. Recursivitatea constă în faptul că în definiția unei funcție apare apelul ei însăși. Acest apel, care apare în însăși definiția funcției, se numește autoapel. Primul apel, făcut în altă funcție, se numește apel principal.

Probleme rezolvate

Problema 1
Sa se scrie o functie recursiva care calculeaza si returneaza diferenta dintre suma elementelor de pe pozitii pare si cea a celor aflate pe pozitii impare dintr-un vector A primit ca parametru impreuna cu n reprezentand numarul lui de elemente. Elementele tabloului sunt indexate de la 1. Exemplu: Daca functia primeste tabloul A={4,5,6,3,2,9} cu n=6, atunci va returna 5 adica (5+3+9)-(4+6+2).

Rezolvare

     
        int dif_poz(int A[], int n)
        {
            if(n==0) return 0;
            else if(n%2==0) return dif_poz(A,n-1)+A[n];
                 else return dif_poz(A,n-1)-A[n];
        }
    

Problema 2

Scrieti o functie recursiva care primeste ca paramentru un numar natural n si returneaza numarul obtinut din n prin eliminarea cifrelor impare.

                int stergimp(int n)
                {
                    if(n==0) return 0;
                    else if(n%2==1) return stergimp(n/10);
                         else return stergimp(n/10)*10+n%10;
                }
               

Rezolvare
    #include < fstream>
        using namespace std;
        ifstream fin("i.in");
        ofstream fout("i.out");
        
        int X[21],Q[21],n,a,b,p,q;
        
        void afisare(int k)
        {
            for(int i=1;i<=k;i++)
                fout<=a && k<=b && pp>=p) afisare(k);
                        back(k+1,pp);
                    }
                    pp=pp-Q[X[k]];
                }
        }
        
        int main()
        {
            fin>>n>>a>>b>>p>>q;
            for(int i=1;i<=n;i++)
                fin>>Q[i];
            back(1,0);
            return 0;
        }

Probleme propuse

1)Se citeste un vector cu n elemente numere naturale (n<=100). Sa se inlocuiasca fiecare element al vectorului cu suma cifrelor cu aceeasi paritate ca si indicele elementului. Indexarea elementelor incepe de la 1. Se vor scrie si folosi functii recursive pentru:

         - citirea vectorului
        - afisarea vectorului
        - calculul sumei cifrelor de o anumita paritate
        - inlocuirea ceruta
        Exemplu: Pentru datele de mai jos
        7
        223 435 6667 24 55 662 122
        Sirul rezultat este
        3 4 7 6 10 14 1
        

2) Se citeste un numar natural n cu cel mult 9 cifre. Afisati numarul de cifre distincte ale lui n. Se vor folosi exclusiv subprograme recursive.

  Exemplu:
        Pentru n=38837 se afiseaza 3 (cifrele distinte sunt 3,7 si 8).

3) Se citeste un numar natural n (n<=20). Afisati un desen format din caracterul * ca in exemplul de mai jos. Se vor folosi exclusiv subprograme recursive. Exemplu:

        Pentru n=3 se afiseaza
*
**
***
**
*
    

4) Se citeste un numar natural n. Sa se descompuna ca suma de puteri crescatoare ale lui 2. Se vor folosi doar prelucrari/calcule realizate cu ajutorul functiilor implementate recursiv. Exemplu: Pentru n=84 va afisa 4 16 64 (84 se descompune ca 4+16+64)

5) a) Scrieti o functie recursiva litera cu doi parametri s si c unde s e un cuvant, iar c este o litera si care returneaza de cate ori apare litera c in cuvantul s. b) Scrieti o functie recursiva litere cu trei parametri s, n si c unde s e un vector ce memoreaza cel mult 20 de cuvinte, n e numar natural reprezentand numarul de cuvinte din vectorul s, iar c este o litera si care returneaza de cate ori apare litera c in total in cele n cuvinte din vectorul s (va folosi functia litera). c) Se citeste un numar n si un vector s de n cuvinte. Folosind functia litere, determinati si afisati literele care apar de un numar maxim de ori in cuvintele din vectorul s. Exemplu: n=3, s={"ana", "are", "mere"} => a e