Clasa a 7-a Lecția 7: Recursivitate (1)

Înregistrare video lecție

Despre recursivitate

O funcție este recursivă dacă se autoapelează. A scrie o funcție recursivă necesită, inițial, o încredere în faptul că funcția funcționează. În fapt, când pornim să scriem o funcție recursivă este bine să considerăm că ea deja funcționează!

Reguli de scriere a unei funcții recursive:

Înainte de a scrie cod este bine să ne clarificăm formula recurentă.
Tratăm mai întâi cazurile simple, atunci când funcția poate returna o valoare fără a se autoapela.
În final, tratăm cazul de recursie, considerând că funcția este deja scrisă pentru cazurile mai mici, folosindu-ne de formula recurentă găsită la început.

Iată un videoclip de prezentare cu exemple de funcții recursive, cu imagini *:

* Exemplele de cod din film sunt scrise într-un pseudocod, suficient de bine explicate astfel încât să fie ușor redactate în orice limbaj de programare, inclusiv C.

Exemple introductive

Factorial

Calcul n! Ne vom folosi de definiția recursivă: $n!={\begin{cases}1,&{\mbox{dacă }}n=1\\n\cdot (n-1)!,&{\mbox{dacă }}n>1.\end{cases}}$

int fact( int n ) {
  if ( n == 1 )
    return 1;
  return n * fact( n - 1 );
}

Putere

Calcul aⁿ. Ne vom folosi de definiția recurentă: $a^{n}={\begin{cases}1,&{\mbox{dacă }}n=0\\a\cdot a^{n-1},&{\mbox{dacă }}n>0.\end{cases}}$

int putere( int a, int n ) {
  if ( n == 0 )
    return 1;
  return a * putere( a, n - 1 );
}

Cmmdc

Calcul cmmdc a două numere. Ne vom folosi de definiția recursivă a lui Euclid: $cmmdc(a,b)={\begin{cases}a,&{\mbox{dacă }}b=0\\cmmdc(b,a{\bmod {b}}),&{\mbox{dacă }}b>0.\end{cases}}$

int cmmdc( int a, int b ) {
  if ( b == 0 )
    return a;
  return cmmdc( b, a % b );
}

Exerciții

Încercați să scrieți următoarele funcții recursive.

Fibonacci

Să se scrie o funcție recursivă care, dat n, calculează al n-lea termen din șirul lui Fibonacci: 0 1 1 2 3 5 8 13.... Ne vom folosi de definiția recurentă: $fib(n)={\begin{cases}0,&{\mbox{dacă }}n=1\\1,&{\mbox{dacă }}n=2\\fib(n-1)+fib(n-2),&{\mbox{dacă }}n>2.\end{cases}}$

int fib( int n ) {
  if ( n == 1 )
    return 0;
  if ( n == 2 )
    return 1;
  return fib( n - 1 ) + fib ( n - 2 );
}

Suma cifrelor unui număr

Să se scrie o funcție recursivă care calculează suma cifrelor unui număr n.

Ne vom folosi de următoarea formulă recurentă: $suma(n)={\begin{cases}0,&{\mbox{dacă }}n=0\\n\%10+suma(n/10),&{\mbox{dacă }}n>0.\end{cases}}$

int sumac( int n ) {
  if ( n == 0 )
    return 0;
  return n % 10 + sumac( n / 10 );
}

Putere în O(log n)

Calculați aⁿ în mod cît mai eficient (a și n numere naturale). Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic. Ideea din spatele acestei rezolvări este următoarea:

Dacă n este par, atunci aⁿ = a^2*n/2 = (a²)^n/2
Dacă n este impar, atunci n-1 este par și avem aⁿ = a * a^n-1 = a * a^2*(n-1)/2 = a * (a²)^(n-1)/2 = a * (a²)^n/2

Rezultă formula de recurență:

$a^{n}={\begin{cases}1,&{\mbox{dacă }}n=0\\{(a^{2})}^{n/2},&{\mbox{dacă }}n>0,n\%2=0\\a\times {(a^{2})}^{n/2},&{\mbox{dacă }}n>0,n\%2=1\end{cases}}$

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile când n este impar vom acumula valoarea curentă a lui a la produsul calculat. Iată soluția bazată pe această idee:

int putere( int a, int n ) {
  int p;

  if ( n == 0 )
    return 1;
  p =  putere( a * a, n / 2 );
  if ( n % 2 ) // n impar?
    p *= a;

  return p;
}

Afișare

Să se afișeze un șir de caractere în ordine inversă. Șirul se termină cu '\n'.

Ne vom folosi de următoarea idee: citim un caracter, apoi chemăm funcția recursivă pentru a afișa restul caracterelor, apoi afișăm caracterul.

void afisare( FILE *fin, FILE *fout ) {
  char ch;

  ch = fgetc( fin );
  if ( ch != '\n' ) {
    afisare( fin, fout );
    fputc( ch, fout );
  }
}

Descompunere în baza 2

Să se scrie o funcție recursivă care, dat n, îl afișează în baza 2.

Similar cu exercițiul precedent, vom calcula ultima cifră a descompunerii (restul împărțirii la doi), apoi vom chema funcția cu n / 2, iar la revenire vom afișa cifra.

void baza2( int n, FILE *fout ) {
  int cf2;

  if ( n > 0 ) {
    cf2 = n % 2;
    baza2( n / 2, fout );
    fprintf( fout, "%d", cf2 );
  }
}

Interclasare vectori ordonați

Dîndu-se doi vectori ordonați să se calculeze un al treilea vector ordonat ce conține elementele lor.

Funcția va primi ca parametri cei trei vectori și pozițiile curente în ei (inițial pozițiile de start, 0). La fiecare apel va alege un element pe care îl va copia. Apoi se va reapela cu indici actualizați (i1 și i3 sau i2 și i3).

void interclaseaza( int n1, int v1[], int n2, int v2[], int v3[],
                   int i1, int i2, int i3 ) {
  if ( i1 < n1 ) { // mai avem elemente in primul vector?
    if ( i2 < n2 && v2[i2] < v1[i1] ) { // v2[i2] exista si e mai mic?
      v3[i3] = v2[i2];                  // copiem v2[i1]
      interclaseaza( n1, v1, n2, v2, v3, i1, i2 + 1, i3 + 1 );
    } else {
      v3[i3] = v1[i1];                  // copiem v1[i1]
      interclaseaza( n1, v1, n2, v2, v3, i1 + 1, i2, i3 + 1 );
    }
  } else if ( i2 < n2 ) { // mai avem elemente in v2? (v1 s-a terminat)
    v3[i3] = v2[i2];
    interclaseaza( n1, v1, n2, v2, v3, i1, i2 + 1, i3 + 1 );
  }
}

Clasa a 7-a Lecția 7: Recursivitate (1)

Contents