10 2018 Lectia19

Lecție

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.

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}}$

#include<cstdio>

using namespace std;

int recurs( int a, int b ){
  if( b == 0 )
    return 1;
  return a * recurs( a, b - 1 );
}

int main(){
  int a, b;
  scanf("%d%d", &a, &b);
  printf("%d\n", recurs(a, b));

  return 0;
}

Putere în timp logaritmic

Putem calcula aⁿ mai rapid folosindu-ne de o altă formulă recurentă: $a^{n}={\begin{cases}1,&{\mbox{dacă }}n=0\\{(a^{2})}^{n/2},&{\mbox{dacă }}n\%2=0\\{(a^{2})}^{n/2}*a,&{\mbox{dacă }}n\%2=1\end{cases}}$

long long logputere( long long baza, int exp ){
  if (exp == 0)
    return 1LL;
  else if ( exp % 2 == 0 )
    return logputere( baza * baza, exp / 2 );
  else
    return logputere( baza * baza, exp / 2 ) * baza;
}

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 în clasă 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 recursivă: $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

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 );
}

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 );
}

Descompunerea î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 );
  }
}

Optimizarea recursivității prin memoizare

Tehnica memoizării ne permite foarte simplu să scădem timpul de execuție al programului folosind mai multă memorie. Această tehnică este cu atât mai eficientă cu cât ne așteptăm să apelăm de multe ori aceeași funcție cu aceiași parametri.

Această tehnică se poate aplica pentru orice funcție dar de regulă se justifică în cazul funcțiilor recursive.

Fibonacci

Pentru aplicarea memoizării la calculul numerelor Fibonacci vom folosi un vector de dimensiune 1 + valoarea maximă a parametrului funcției în care vom stoca valorile pe care le returnează funcția. Inițial toate valorile vectorului sunt 0, cu semnificația că numerele Fibonacci sunt încă necalculate. După calcularea uneia dintre valorile funcției aceasta este memorată în vector. Dacă funcția recursivă este reapelată cu același parametru atunci nu vom mai efectua calculul ci vom returna direct valoarea stocată în vector.

const int MAX_NF = 70;
long long Fibonacci[1 + MAX_NF];

long long fibonacci(int n) {
  if (Fibonacci[n] == 0)
    if (n == 1 || n == 2)
      Fibonacci[n] = 1;
    else
      Fibonacci[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return Fibonacci[n];
}

CMMDC

Dacă vrem să aplicăm tehnica memoizării pentru calculul recursiv al cmmdc-ului a două numere, atunci vom avea nevoie să alocăm o matrice, așa cum am ilustrat mai jos.

Tehnica poate fi generalizată pentru funcții recursive cu oricâți parametri, folosind matrice cu mai multe dimensiuni. Singura restricție de care trebuie să ținem cont este memoria. Observați că doar pentru calculul cmmdc-ului a două numere naturale mai mici sau egale cu 100 deja alocăm o matrice de 101*101 elemente.

const int MAX_A = 100;
const int MAX_B = 100;
unsigned short int Cmmdc[1 + MAX_A][1 + MAX_B];

unsigned short int cmmdc(unsigned short int a, unsigned short int b) {
  if (Cmmdc[a][b] == 0)
    if(b == 0)
      Cmmdc[a][b] = a;
    else
      Cmmdc[a][b] = cmmdc(b, a % b);
  return Cmmdc[a][b];
}

Interclasarea a doi vectori prin recursivitate

Dându-se 3 vectori:

• vectorul 1 prin pointeri către începutul și după sfârșitul lui;
• vectorul 2 prin pointeri către începutul și după sfârșitul lui;
• vectorul 3 printr-un pointer către începutul lui

și garantându-se că:

• elementele vectorilor 1 și 2 sunt în ordine crescătoare;
• vectorul 3 are rezervat un spațiu cel puțin egal cu suma lungimilor vectorilor 1 și 2,

să se scrie o funcție recursivă care primește ca parametri cei 3 vectori și îi interclasează pe primii 2 în al treilea.

Implementare

La oră am implementat această problemă în 3 iterații. În prima iterație am folosit indici pentru a reține unde am ajuns în cei doi vectori și întregi pentru a reține lungimea vectorilor. În a doua iterație am folosit pointeri în loc de indici. Iar în a treia iterație am folosit pointeri pentru a memora unde se termină vectorii.

const int MAX_N = 100000;
const int MAX_M = 100000;

int V1[MAX_N];
int V2[MAX_M];
int V3[MAX_N + MAX_M];

void interclaseaza(int i1, int i2, int i3, int n1, int n2) {
  // i3 == i1 + i2
  if (i1 < n1 && i2 < n2) {
    if (V1[i1] < V2[i2]) {
      V3[i3] = V1[i1];
      interclaseaza(i1 + 1, i2, i3 + 1, n1, n2);
    } else {
      V3[i3] = V2[i2];
      interclaseaza(i1 , i2 + 1 , i3 + 1 , n1 , n2);
    }
  } else if (i1 < n1) {
    V3[i3] = V1[i1];
    interclaseaza(i1 + 1 , i2 , i3 + 1 , n1 , n2);
  } else if(i2 < n2) {
    V3[i3] = V2[i2];
    interclaseaza(i1 , i2 + 1 , i3 + 1 , n1 , n2);
  } else {
    // vectorii v1 si v2 au fost goliti si nu facem nimic
    // => se opreste recursivitatea
  }
}

void interclaseazaP(int *v1, int *v2, int *v3, int n1, int n2) {
  if (n1 > 0 && n2 > 0) {
    if (*v1 < *v2) {
      *v3 = *v1;
      interclaseazaP(v1 + 1, v2, v3 + 1, n1 - 1, n2);
    } else {
      *v3 = *v2;
      interclaseazaP(v1, v2 + 1, v3 + 1, n1, n2 - 1);
    }
  } else if (n1 > 0) {
    *v3 = *v1;
    interclaseazaP(v1 + 1, v2, v3 + 1, n1 - 1, n2);
  } else if (0 < n2) {
    *v3 = *v2;
    interclaseazaP(v1, v2 + 1, v3 + 1, n1, n2 - 1);
  } else {
    // vectorii v1 si v2 au fost goliti si nu facem nimic
    // => se opreste recursivitatea
  }
}

void interclaseazaP2(int *v1, int *v2, int *v3, int *v1sf, int *v2sf) {
  if (v1 < v1sf && v2 < v2sf) {
    if (*v1 < *v2) {
      *v3 = *v1;
      interclaseazaP2(v1 + 1, v2, v3 + 1, v1sf, v2sf);
    } else {
      *v3 = *v2;
      interclaseazaP2(v1, v2 + 1, v3 + 1, v1sf, v2sf);
    }
  } else if (v1 < v1sf) {
    *v3 = *v1;
    interclaseazaP2(v1 + 1, v2, v3 + 1, v1sf, v2sf);
  } else if (v2 < v2sf) {
    *v3 = *v2;
    interclaseazaP2(v1, v2 + 1, v3 + 1, v1sf, v2sf);
  } else {
    // vectorii v1 si v2 au fost goliti si nu facem nimic
    // => se opreste recursivitatea
  }
}
// Timp: O(N + M)
// Spatiu: O(1)

int main(void) {
  int N, M;
  int i;

  // citirea datelor
  scanf("%d", &N);
  for (i = 0; i < N; ++i) {
    scanf("%d", &V1[i]);
  }
  scanf("%d", &M);
  for (i = 0; i < M; ++i) {
    scanf("%d", &V2[i]);
  }

  // calcularea solutiei
  interclaseaza(0, 0, 0, N, M);
  interclaseazaP(V1, V2, V3, N, M);
  interclaseazaP2(V1, V2, V3, V1 + N, V2 + M);

  // afisarea solutiei
  for (i = 0; i < N + M; ++i) {
    printf("%d ", V3[i]);
  }
  printf("\n");
  return 0;
}

Temă

• Tema 3 clasa a 7-a:
  • Sumadiv: să se scrie o funcție recursivă care să calculeze suma divizorilor unui număr. Ea va arăta astfel:

    int sumd( int n, int d ) {
      ...
    }

    și va fi apelată inițial astfel:

    sum = sumd( n, 1 );

    Semnificaţia este suma divizorilor lui n care sînt mai mari sau egali cu d şi mai mici sau egali cu n / d. Mai exact trebuie să completați funcția sumd din programul următor:

    #include <stdio.h>
    
    int sumd( int n, int d ) {
      ...
    }
    
    int main() {
      FILE *fin, *fout;
      int n;
    
      fin = fopen( "sumadiv.in", "r" );
      fscanf( fin, "%d", &n );
      fclose( fin );
    
      fout = fopen( "sumadiv.out", "w" );
      fprintf( fout, "%d\n", sumd( n, 1 ) );
      fclose( fout );
    
      return 0;
    }

    Atenţie mare la complexitatea algoritmului obţinut!
  • Invector Să se răstoarne un vector folosind o funcție recursivă. Vectorul trebuie modificat, nu doar afișat invers. Funcția va arăta astfel:

    void inv( int primul, int ultimul, int v[] ) {
      ...
    }

    unde primul și ultimul sînt indicii de început, respecitiv sfîrșit care definesc subvectorul de răsturnat. Funcția va fi apelată inițial astfel:

    inv( 0, n-1, v );

    Mai exact trebuie să completați funcția inv din programul următor:

    #include <stdio.h>
    
    int v[100000];
    
    void inv( int primul, int ultimul, int v[] ) {
      ...
    }
    
    int main() {
      FILE *fin, *fout;
      int n, i;
    
      fin = fopen( "invector.in", "r" );
      fscanf( fin, "%d", &n );
      for ( i = 0; i < n; i++ )
        fscanf( fin, "%d", &v[i] );
      fclose( fin );
    
      inv( 0, n-1, v );
    
      fout = fopen( "invector.out", "w" );
      for ( i = 0; i < n; i++ )
        fprintf( fin, "%d ", v[i] );
      fprintf( fin, "\n" );
      fclose( fout );
    
      return 0;
    }

  • V (ONI 2004 clasa a 7-a) Clasa a 7-a poate să ia doar 50% din punctaj. Clasa a 8-a trebuie să ia 100%
• Opțional, grea: Combinări ${C}_{n}^{k}$- combinări de n luate cîte k. Date numerele naturale n și k, k ≤ n, să se afișeze toate submulțimile mulțimii {1, 2, 3, ..., n} de k elemente.

Rezolvări aici [1]