a IX-a A27 lecții INFORMATICĂ | 30 lecții T.I.C.
Informatică
█
Lectia 00001   |   Lectia 00   |   Lectia 01   |   Lectia 02   |   Lectia 03   |   Lectia 04   |   Lectia 05   |   Lectia 06   |   Lectia 07   |   Lectia 08   |   Lectia 09   |   Lectia 10   |   Lectia 101   |   Lectia 102   |   Lectia 103   |   Lectia 11   |   Lectia 11_2   |   Lectia 12   |   Lectia 12_2   |   Lectia 12_3   |   Lectia 12_4   |   Lectia 12_5   |   Lectia 13   |   Lectia 14   |   Lectia 17
█
Lectia 18   |   Lectia 19
T.I.C.

█
Lectia 01   |   Lectia 02   |   Lectia 03   |   Lectia 04
█
Lectia 05   |   Lectia 06   |   Lectia 07   |   Lectia 08   |   Lectia 09
█
Lectia 10   |   Lectia 11   |   Lectia 12   |   Lectia 13   |   Lectia 14   |   Lectia 15   |   Lectia 16   |   Lectia 17   |   Lectia 18   |   Lectia 19   |   Lectia 19   |   Lectia 20   |   Lectia 23   |   Lectia 24   |   Lectia 26   |   Lectia 27   |   Lectia 28   |   Lectia 29   |   Lectia 30_2   |   Lectia 31   |   Lectia 32
a IX-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a IX-a C0 lecții INFORMATICĂ | 26 lecții T.I.C.
T.I.C.
█
Lectia 01   |   Lectia 02   |   Lectia 03   |   Lectia 04
█
Lectia 05   |   Lectia 06   |   Lectia 07   |   Lectia 08
█
Lectia 10   |   Lectia 12   |   Lectia 13   |   Lectia 14   |   Lectia 15   |   Lectia 16   |   Lectia 17   |   Lecția 18   |   Lectia 19   |   Lectia 20   |   Lectia 21   |   Lectia 22   |   Lectia 23   |   Lectia 24   |   Lectia 25   |   Lectia 26   |   Lectia 27   |   Lectia 28
a IX-a D0 lecții INFORMATICĂ | 0 lecții T.I.C.
a IX-a E0 lecții INFORMATICĂ | 0 lecții T.I.C.
a X-a A6 lecții INFORMATICĂ | 22 lecții T.I.C.
Opțional
█
Fișa 01   |   Fișa 02   |   Fișa 03   |   Fișa 04   |   Fișa 05   |   Lectia 20
T.I.C.

█
Lectia 07   |   Lectia 08   |   Lectia 09   |   Lectia 10   |   Lectia 11   |   Lectia 12   |   Lectia 13   |   Lectia 14
█
Lecția 14_1
█
Lectia 15
█
Lectia 16   |   Lectia 17   |   Lectia 19   |   Lectia 20
█
Lectia 21   |   Lecția 22   |   Lectia 23   |   Lectia 24   |   Lectia 25   |   Lectia 26   |   Lectia 27   |   Lectia 28
a X-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a X-a C0 lecții INFORMATICĂ | 0 lecții T.I.C.
a X-a D0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XI-a A30 lecții INFORMATICĂ | 0 lecții T.I.C.
Informatică
█
Lectia 07   |   Lectia 08   |   Lectia 09   |   Lectia 10   |   Lectia 11   |   Lectia 12   |   Lectia 13   |   Lectia 14
█
Lectia 16   |   Lectia 18   |   Lectia 19   |   Lectia 20   |   Lectia 21
█
Lectia 23
Lectia 23 --- [ Teorie + 3 Probleme rezolvate ]

SUBPROGRAME RECURSIVE

  • Ce este recursivitatea ?
    • Recursivitatea este un concept matematic care implică definirea unui concept prin referirea la același concept.
    • Astfel, mulțimea numerelor naturale se poate defini:
      • 1 este număr natural
      • orice succesor al unui număr natural este de asemenea un număr natural
      • În definiția de mai sus, observăm că avem o valoare inițială (1), iar restul valorilor se obțin adunând 1 la valoarea anterioară

Spunem despre un subprogram că este recursiv dacă conține în definirea sa un apel la el însuși.

Astfel putem avea două tipuri de recursivitate:

  • Directă (atunci când subprogramul conține un apel la el însuși)
  • Indirectă (atunci când subprogramul P apelează un subprogram Q care la rândul să conține în definirea sa un apel la subprogramul P).

Structura unei funcţii recursive

tip nume_funcţie (lista de parameri) {

 .................

nume_funcţie (lista de parametri);       

//funcţia conține un apel la ea însăși

 .................. 

} 

 

                Structura unei funcţii recursive indirect apelate prin                                  intermediul unei alte funcţii:

          tip B(lista de parameri) {

                 .................

            A(lista de parametri); //funcţia B apelează funcţia A ..................

           }

          tip A(lista de parameri) //funcţia A este recursivă şi apelează funcţia B                             {.................

                                  if(condiţie de continuare)

                                           .................

                                 B(lista de parametri);

                           .................. }

Majoritatea algoritmilor repetitivi se pot implementa atât în varianta nerecursivă, folosind cicluri, cât și în varianta recursivă. Varianta recursivă este recomandată în special pentru problemele definite prin relații de recurentă, care permit o formulare a rezultatelor mult mai clară și mai concisă.

Un subprogram recursiv se caracterizează prin proprietatea că se auto-apelează, adică din interiorul lui se apelează pe el însuși. Din afara subprogramului facem un prim apel al acestuia, după care subprogranul se auto-apelează de un anumit număr de ori: la fiecare nouă auto-apelare a subprogramului, se execută din nou secvența de instrucțiuni ce reprezintă corpul său, eventual cu alte date, creându-se un așa-numit „lanț de auto-apeluri recursive”.

Putem spune că un subprogram recursiv are același efect ca și un ciclu: repetă execuția unei anumite secvențe de instrucțiuni. Dar, la fel ca în cazul unui ciclu, este necesar ca repetarea să nu aibă loc la infinit. De aceea în corpul subprogramului trebuie să existe cel puțin o testare a unei condiții de oprire, la îndeplinirea căreia se întrerupe lanțul de auto-apeluri.

int f(int n)

{

     if (n==0) return 1;

    else return n*f(n-1);

}

int main()

{  int n;

    cout<<“n=“; cin>>n ;

    cout << n <<“! = “<<f(n));

}

Funcţia factorial este scrisă după definiţia recursivă, respectiv varianta iterativă:
 

int f (int n)

{ int i,P=1;

   for (i=1; i<= n; i++) P=P*i;

     return P;

}

  • Cum afişăm numerele naturale de la 1 la n printr-o procedură recursivă ?
  • Rezolvare: În acest caz, nu avem o formulă de recurenţă pentru scrierea unui subprogram recursiv. Pentru a rezolva problema o descompunem în mai multe subprobleme de acelaşi tip:
  • Subproblema p(i): pentru valoarea i a parametrului vom tipări i după care apelăm (recursiv) p pentru i+1
  • Apelul iniţial este p(1) : începem cu 1
  • Condiţia de oprire este să ajungem la n, când tipărim doar n fără alte apeluri
 
 

int n ;                                     // câte numere tipărim

void p(int i)                         // procedura p cu parametrul i

{

    if (i==n) cout<<n ;    // rezolvarea directă (condiţia de STOP)

     else {

            cout<<i<<;           // Subproblema p(i): tipărim i

            p(i+1);                      // trecem la subproblema p(i+1)

             }

}

int main()

{  cout<<“n=“;  cin>>n;      // citim valoarea lui n

  p(1);                     &am p;am p;nbs p;              // apelul iniţial

}

Cum scriem un subprogram recursiv ?

     1. Trebuie să formulăm problema în termeni recursivi

                - stabilim formula de recurenţă

                - identificăm soluţia în cazul rezolvării directe, dată de obicei sub forma condiţiilor iniţiale

                - formulăm subproblemele de rezolvat în cazul în care nu dispunem de o formulă de recurenţă

  1. Scriem subprogramul recursiv:

                - soluţia directă se scrie sub forma condiţiei de oprire

                - apelul recursiv rezultă din formula de recurenţă

                - la fiecare apel problema parţială trebuie rezolvată complet

1. Sa se scrie un subprogram C++ recursiv care determina suma cifrelor unui numar natural.
Propune o soluție

S
o
l
u
ț
i
a:
Introdu următorul text: 125418109
#include <iostream>
using namespace std;
long n;
int SumaCifre(long a)
{
    if(a<10)
        return a;
    else
        return a%10+SumaCifre(a/10);
}
int main(){
cout<<"n=";
cin>>n;
cout<<"Suma cifrelor a lui "<<n<<" este "<<SumaCifre(n);
return 0;
}
2. Sa se scrie un subprogram C++ recursiv care determina numarul de cifre ale unui numar natural.
Propune o soluție

S
o
l
u
ț
i
a:
Introdu următorul text: 879041696
#include <iostream>
using namespace std;
long n;
int NumarCifre(long a)
{
    if(a<10)
        return 1;
    else
        return 1+NumarCifre(a/10);
}
int main(){
cout<<"n=";
cin>>n;
cout<<"Numarul de cifre a lui "<<n<<" este "<<NumarCifre(n);
return 0;
}
3. Sa se scrie un subprogram C++ recursiv care determina prima cifra a unui numar natural.
Propune o soluție

S
o
l
u
ț
i
a:
Introdu următorul text: 696040059
#include <iostream>
using namespace std;
long n;
int PrimaCifra(long a)
{
    if(a<10)
        return a;
    else
        return PrimaCifra(a/10);
}
int main(){
cout<<"n=";
cin>>n;
cout<<"Prima cifra a lui "<<n<<" este "<<PrimaCifra(n);
return 0;
}
Fii primul care comentează lecţia
     Submit
  |   Lectia 24
█
Lectia 36
█
Lectia 40   |   Lectia 41   |   Lectia 42   |   Lectia 43   |   Lectia 44   |   Lectia 45   |   Lectia 46   |   Lectia 46_1
█
Lectia 47   |   Lectia 48   |   Lectia 49   |   Lectia 50   |   Lectia 50_1
█
Lectia 50_2
a XI-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XI-a C0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XI-a D0 lecții INFORMATICĂ | 14 lecții T.I.C.
T.I.C.
█
Fişa 01   |   Fişa 02   |   Fişa 03   |   Fişa 04   |   Fişa 05   |   Fişa 06   |   Fişa 07
█
Lectia 01   |   Lectia 02   |   Lectia 03   |   Lectia 04   |   Lectia 05   |   Lectia 06   |   Lectia 07
a XI-a E0 lecții INFORMATICĂ | 1 lecții T.I.C.
T.I.C.
█
Fişa 01
a XII-a A2 lecții INFORMATICĂ | 0 lecții T.I.C.
Informatică
█
Lectia 01   |   Lectia 02
a XII-a B0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XII-a C0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XII-a D0 lecții INFORMATICĂ | 0 lecții T.I.C.
a XII-a E0 lecții INFORMATICĂ | 0 lecții T.I.C.
Excelenta A0 lecții INFORMATICĂ | 0 lecții T.I.C.