View source for Clasa a 7-a Lecția 8: Recursivitate (2)

== Înregistrare video lecție ==

<youtube height="720" width="1280">https://youtu.be/yPXRdAuZv6w</youtube>


== Exemple de funcții recursive ==

Iată câteva probleme care se rezolvă ușor cu funcții recursive:


=== Palindrom ===

Verificare palindrom: 

<syntaxhighlight lang="c" line>
#include <stdio.h>

int putere( int n ) {             // calculam recursiv cea mai mare
  int p = 1;                      // putere a lui 10 mai mica decit n

  if ( n < 10 )                   // cand n are o singura cifra
    return 1;                     // cea mai mare putere este 1
  return 10 * putere( n / 10 );   // adaugam un zero si taiem o cifra
}

int palindrom( int n, int p10 ) { // pe baza lui n si a puterii lui 10
  if ( n < 10 )                   // un numar de o cifra este palindrom
    return 1;
  if ( n / p10 != n % 10 )        // testam prima si ultima cifra
    return 0;
  return palindrom( n % p10 / 10, p10 / 100 ); // taie prima si ultima cifra
}

int main() {
  int n, pow10;

  scanf( "%d", &n );
  pow10 = putere( n );
  if ( palindrom( n, pow10 ) )
    printf( "%d este palindrom\n", n );
  else
    printf( "%d nu este palindrom\n", n );
  return 0;
}
</syntaxhighlight>


=== Permutări ===

Dându-se <source lang="C" enclose="none">n</source> să se afișeze toate permutările mulțimii numerelor de la 1 la <source lang="C" enclose="none">n</source> în ordine lexicografică. 

<syntaxhighlight lang="c" line>
#include <stdio.h>

int v[10];
char folosit[10];

void perm( int n, int poz ) {
  int i;

  if ( poz >= n ) {             // daca am umplut n pozitii
    for ( i = 0; i < n; i++ )   // afiseaza combinarea curenta
      printf( "%d ", v[i] );
    printf( "\n" );
  } else
    for ( v[poz] = 1; v[poz] <= n; v[poz]++ )
      if ( !folosit[v[poz]] ) { // daca elementul curent nu e deja folosit
        folosit[v[poz]] = 1;    // marcheaza-l ca folosit
        perm( n, poz + 1 );     // genereaza restul permutarii
        folosit[v[poz]] = 0;    // demarcheaza elementul
      }
}

int main() {
  int n;

  scanf( "%d", &n );
  perm( n, 0 );
  return 0;
}
</syntaxhighlight>


Ce complexitate are acest algoritm?

Calculul depășește nivelul acestei lecții. Dar putem vedea că este ineficient: pe măsură ce plasăm numere în vector și vectorul <source lang="C" enclose="none">folosit[]</source> se ''umple'', vom plasa pe poziția curentă tot mai puține numere, dar le vom parcurge pe toate <source lang="C" enclose="none">n</source>. Cum am putea îmbunătăți algoritmul? Cumva ar fi bine să parcurgem doar elementele pe care le vom plasa. Avem, deci, nevoie ca la fiecare poziție să avem o mulțime a numerelor rămase de plasat, mulțime pe care să o putem parcurge în ''O(n - poz)'' și nu în ''O(n)''.

Avem două idei:


==== Permutări cu interschimbare (swap) ====

Am putea să menținem acea mulțime chiar în vectorul <source lang="C" enclose="none">v[]</source>. Convenția este că dacă am ajuns la poziția <source lang="C" enclose="none">poz</source> am plasat deja <source lang="C" enclose="none">poz</source> elemente, iar cifrele rămase for fi în vector la pozițiile <source lang="C" enclose="none">poz..n-1</source>.

Vom scrie, la început, numerele de la 1 la <source lang="C" enclose="none">n</source> în vectorul <source lang="C" enclose="none">v[]</source>. Vrem să plasăm un element pe poziția <source lang="C" enclose="none">poz</source>. El va fi ales de pe o poziția <source lang="C" enclose="none">i</source> care se află după <source lang="C" enclose="none">poz</source>, <source lang="C" enclose="none">i ≤ poz</source>. Vom interschimba, deci, elementele aflate pe pozițiile <source lang="C" enclose="none">poz</source> și <source lang="C" enclose="none">i</source>. Aceasta îmi garantează că elementele rămase pe pozițiile <source lang="C" enclose="none">poz+1..n-1</source> sunt elemente încă nefolosite în permutare. Putem apela recursiv funcția. La revenire vom repune elementele în poziția originală, prin încă o interschimbare a elementelor la poziția <source lang="C" enclose="none">poz</source> și <source lang="C" enclose="none">i</source>.

Avantajul acestei metode este clar, va parcurge doar elementele plasate. Are și vreun dezavantaj?

Dezavantajul este că permutările nu vor fi generate în ordine lexicografică. În funcție de aplicație acest lucru s-ar putea să nu conteze.


==== Permutări cu liste ====

Am putea să menținem elementele în ordinea lor crescătoare într-o listă. Atunci când folosim un element, plasându-l pe poziția poz, îl eliminăm din listă. Apoi reapelăm. La revenirea din apel plasăm elementul înapoi în listă și trecem la următorul element.

Această metodă, implementată corect, este mai rapidă și generează și permutările în ordine lexicografică, deoarece elementele din listă sunt permanent în ordinea inițială.


=== Plată suma ===

Moduri plată suma cu monede 1, 2, 5: 

<syntaxhighlight lang="c" line>
#include <stdio.h>

int mon[3] = { 1, 2, 5 };

int suma( int s, int nrmon ) { // in cite feluri platim s folosind nrmon monede
  if ( nrmon == 0 )            // daca nu mai avem monede
    return 0;                  // nu putem plati (zero moduri de plata)
  if ( s < 0 )                 // o suma negativa nu se poate plati
    return 0;
  if ( s == 0 )                // o suma de zero se plateste intr-un singur fel
    return 1;
  // putem plati in doua feluri de combinatii
  // - fie in combinatii care se termina cu ultima moneda din vector
  // - fie in combinatii care nu folosesc deloc ultima moneda din vector
  return suma( s - mon[nrmon - 1], nrmon ) + suma( s, nrmon - 1 );
}

int main() {
  int s;

  scanf( "%d", &s );
  printf( "%d este platibila in %d moduri\n", s, suma( s, 3 ) );
  return 0;
}
</syntaxhighlight>


== Memoizare (continuare) ==

Anul trecut am vorbit despre [# memoizare]. Am spus atunci că este o metodă de a face un program mai rapid fără a-i schimba modul în care el funcționează. Ideea ei este ca atunci când efectuăm un calcul scump să păstrăm valoarea calculată într-un tablou pentru a economisi timp în cazul când în viitor vom avea din nou nevoie de acea valoare.

Tot atunci am prezentat un exemplu avansat de memoizare folosit într-o funcție recursivă, mai exact în calculul recursiv al unui element din șirul lui Fibonacci.

Merită menționat că tehnica memoizării se aplică mai ales în funcții recursive. Ea 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. De aceea funcția trivială de calcul al unui termen din șirul lui Fibonacci este un exemplu perfect de memoizare, ea avînd un număr exponențial de apeluri, în varianta nememoizată.

'''Important:''' memoizarea nu schimbă logica sau structura algoritmului folosit. Acesta este un mare avantaj. Avem o opțiune între câtă memorie folosim și cât timp câștigăm. Aceste tehnici, în care putem alege între timp și memorie, sunt destul de rare în algoritmică.

Să vedem două exemple clasice de memoizare.


=== Factorial ===

Algoritmul simplu pentru calculul lui n!, fără memoizare, este:

<syntaxhighlight lang="c" line>
long long fact( int n ) {
  if ( n == 1 )
    return 1;
  return n * fact( n - 1 );
}
</syntaxhighlight>


Cel cu memoizare va folosi un vector ce va stoca elementele deja calculate:

<syntaxhighlight lang="c" line>
long long val[20] = { 1 };

// exemplu de funcție factorial implementată folosind memoizare
long long fact( int n ) {
  if ( val[n] == 0 )             // valoare inca necalculata
    val[n] = n * fact( n - 1 );  // o calculam in tabel

  return val[n];
}
</syntaxhighlight>


=== Fibonacci ===

Algoritmul direct de calcul al celui de-al n-lea termen al șirului lui Fibonacci:

<syntaxhighlight lang="c" line>
int fib( int n ) {
  if ( n == 1 || n == 2 )
    return 1;
  return fib( n-1 ) + fib( n-2 );
}
</syntaxhighlight>


Cel cu memoizare va folosi un vector ce va stoca elementele deja calculate:

<syntaxhighlight lang="c" line>
int val[1000] = { 1, 1 };

// exemplu de funcție fibonacci implementată folosind memoizare
int fib( int n ) {
  if ( val[n] == 0 ) // inca necalculat
    val[n] = fib( n-1 ) + fib( n-2 ); // il calculam in tabel
  return val[n]; // returnam valoarea din tabel
}
</syntaxhighlight>


== Recursie Top-Down și Bottom-Up ==

=== Recursie Top-Down ===

Există două moduri de implementare a unei soluții recursive:

Recursie '''Top-Down''': când pornim cu o problemă mai mare și apelăm funcția pentru probleme mai mici pe care le folosim ulterior în apelul curent. În subproblema de bază returnăm un rezultat de bază, cum ar fi zero sau unu. În această categorie sunt aproape toate exemplele de până acum cu excepția cmmdc, interclasare vectori, combinări, permutări și sumă de monede.

=== Recursie Bottom-Up ===

Recursie '''Bottom-Up''': când pornim cu o problemă mai mare și cu un acumulator de soluție, care inițial este vid (zero sau unu), iar în apelurile ulterioare reducem mărimea problemei adăugând (construind) soluția finală în acumulator. Exemplele de combinări și permutări sunt Bottom-Up în care acumulatorul este vectorul și nu este transmis în mod explicit, deși am putea face acest lucru.


=== Exemple de recursie Bottom-Up cu acumulator ===

Implementați bottom-up cu acumulator exemplele făcute până acum.


==== Factorial ====

Iată o comparație a celor două implementări ale funcției factorial, implementată recursiv top-down și bottom-up cu acumulator:

{| class="wikitable"
!Top-down
!Bottom-up
|-
| <syntaxhighlight lang="c" line>
#include <stdio.h>

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

int main() {
  int n;

  scanf( "%d", &n );
  printf( "%d! = %d\n", n, fact( n ) );

  return 0;
}</syntaxhighlight>
| <syntaxhighlight lang="c" line>
#include <stdio.h>

int fact( int n, int ac ) {
  if ( n == 1 )                 // cind n = 1 am terminat calculul in ac
    return ac;
  return fact( n - 1, n * ac ); // adaugam n la acumulator
}

int main() {
  int n;

  scanf( "%d", &n );
  printf( "%d! = %d\n", n, fact( n, 1 ) );

  return 0;
}</syntaxhighlight>
|}


==== Putere ====

Iată o comparație a celor două implementări ale funcției putere, implementată recursiv top-down și bottom-up cu acumulator:

{| class="wikitable"
!Top-down
!Bottom-up
|-
| <syntaxhighlight lang="c" line>
#include <stdio.h>

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

int main() {
  int n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n ) );
  return 0;
}</syntaxhighlight>
| <syntaxhighlight lang="c" line>
#include <stdio.h>

int putere( int a, int n, int ac ) {
  if ( n == 0 ) // cind puterea e zero acumulatorul are rezultatul
    return ac;
  return putere( a, n - 1, a * ac ); // acumuleaza a la rezultat
}

int main() {
  int n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n, 1 ) );
  return 0;
}</syntaxhighlight>
|}


==== CMMDC ====

De remarcat că funcția recursivă care calculează cmmdc a două numere, prezentată în lecția trecută, este deja bottom-up cu acumulator:

<syntaxhighlight lang="c" line>
int cmmdc( int a, int b ) {
  if ( b == 0 )
    return a;
  return cmmdc( b, a % b );
}
</syntaxhighlight>


==== Fibonacci ====

Iată o comparație a celor două implementări ale șirului lui Fibonacci, implementat recursiv top-down și bottom-up cu acumulator:

{| class="wikitable"
!Top-down
!Bottom-up
|-
| <syntaxhighlight lang="c" line>
int fib( int n ) {
  if ( n == 1 )
    return 0;
  if ( n == 2 )
    return 1;
  return fib( n - 1 ) + fib ( n - 2 );
}</syntaxhighlight>

Ea va fi apelată astfel:

<syntaxhighlight lang="c" line>f = fib( 15 );</syntaxhighlight>

Unde 15 este numărul termenului dorit.
| <syntaxhighlight lang="c" line>
int fib( int n, int f1, int f2 ) {
  if ( n == 1 )
    return f1;
  return fib( n - 1, f2, f1 + f2 );
}</syntaxhighlight>

Ea va fi apelată astfel:

<syntaxhighlight lang="c" line>f = fib( 15, 0, 1 );</syntaxhighlight>

Unde 0 și 1 sunt primii doi termeni ai șirului, iar 15 este numărul termenului dorit.
|}


==== Suma cifrelor unui număr ====

Iată o comparație a celor două implementări ale sumei cifrelor unui număr, implementată recursiv top-down și bottom-up cu acumulator:

{| class="wikitable"
!Top-down
!Bottom-up
|-
| <syntaxhighlight lang="c" line>
int sumac( int n ) {
  if ( n == 0 )
    return 0;
  return n % 10 + sumac( n / 10 );
}</syntaxhighlight>

Ea va fi apelată astfel:

<syntaxhighlight lang="c" line>s = sumac( 2324103 );</syntaxhighlight>

Unde 2324103 este numărul căruia îi calculăm suma cifrelor.
| <syntaxhighlight lang="c" line>
int sumac( int n, int suma ) {
  if ( n == 0 )
    return suma;
  return sumac( n / 10, suma + n % 10 );
}</syntaxhighlight>

Ea va fi apelată astfel:

<syntaxhighlight lang="c" line>s = sumac( 2324103, 0 );</syntaxhighlight>

Unde 2324103 este numărul căruia îi calculăm suma cifrelor, iar 0 este inițializarea acumulatorului sumă.
|}


==== Putere în O(log n) ====

Iată o comparație a celor două implementări ale funcției putere, implementată ''O(log n)'' recursiv top-down și bottom-up cu acumulator:

{| class="wikitable"
!Top-down
!Bottom-up
|-
| <syntaxhighlight lang="c" line>
#include <stdio.h>

// a este numărul de ridicat la putere
// n este puterea
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;
}

int main() {
  int n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n ) );
  return 0;
}</syntaxhighlight>
| <syntaxhighlight lang="c" line>
#include <stdio.h>

// in permanenta a^n * ac detine rezultatul
// cind n devine zero a^n * ac = ac, deci rezultatul este chiar ac
int putere( int a, int n, int ac ) {
  if ( n == 0 ) // cind puterea e zero acumulatorul are rezultatul
    return ac;

  if ( n % 2 )                         // cind n impar
    ac *= a;                           // acumuleaza a la rezultat

  return putere( a * a, n / 2, ac );   // totuna cu (a*a)^(n/2)
}

int main() {
  int n, a;

  scanf( "%d%d", &a, &n );
  printf( "%d^%d = %d\n", a, n, putere( a, n, 1 ) );
  return 0;
}



</syntaxhighlight>
|}


==== Interclasare vectori ordonați ====

De remarcat că interclasarea a doi vectori ordonați, prezentată data trecută, este bottom-up cu acumulator (vectorul <source lang="C" enclose="none">v3[]</source> este acumulatorul).

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 (<source lang="C" enclose="none">i1</source> și <source lang="C" enclose="none">i3</source> sau <source lang="C" enclose="none">i2</source> și <source lang="C" enclose="none">i3</source>).

<syntaxhighlight lang="c" line>
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 );
  }
}
</syntaxhighlight>

==== Palindrom ====

Verificarea că un număr este palindrom este, în fapt, mai ușor de scris bottom-up. În acumulator vom construi inversul numărului <source lang="C" enclose="none">n</source>. La final vom compara inversul cu originalul. Iată o comparație a celor două implementări ale testului de palindrom, implementat recursiv top-down și bottom-up cu acumulator:

{| class="wikitable"
!Top-down
!Bottom-up
|-
| <syntaxhighlight lang="c" line>
#include <stdio.h>

int putere( int n ) {             // calculam recursiv cea mai mare
  int p = 1;                      // putere a lui 10 mai mica decit n

  if ( n < 10 )                   // cind n are o singura cifra
    return 1;                     // cea mai mare putere este 1
  return 10 * putere( n / 10 );   // adaugam un zero si taiem o cifra
}

int palindrom( int n, int p10 ) { // pe baza lui n si a puterii lui 10
  if ( n < 10 )                   // un numar de o cifra este palindrom
    return 1;
  if ( n / p10 != n % 10 )        // testam prima si ultima cifra
    return 0;
  return palindrom( n % p10 / 10, p10 / 100 ); // taie prima si ultima cifra
}

int main() {
  int n, pow10;

  scanf( "%d", &n );
  pow10 = putere( n );
  if ( palindrom( n, pow10 ) )
    printf( "%d este palindrom\n", n );
  else
    printf( "%d nu este palindrom\n", n );
  return 0;
}</syntaxhighlight>
| <syntaxhighlight lang="c" line>





#include <stdio.h>

int palindrom( int n, int nc, int ac ) {
  if ( n == 0 )            // cind n=0 ac este inversul lui nc
    return nc == ac;       // daca sint egale, returnam 1, altfel 0
  return palindrom( n / 10, nc, ac * 10 + n % 10 ); // taiem o cifra tin n
}                                                   // si o adaugam la ac

int main() {
  int n;

  scanf( "%d", &n );
  if ( palindrom( n, n, 0 ) )
    printf( "%d este palindrom\n", n );
  else
    printf( "%d nu este palindrom\n", n );
  return 0;
}</syntaxhighlight>
|}

=== Transformarea recursiei din Top-Down în Bottom-Up ===

Orice funcție recursivă de tip Top-Down care pe orice cale de execuție are un singur apel recursiv se poate transforma într-o funcție de tip Bottom-Up prin adăugarea unui parametru acumulator. De ce ne interesează acest lucru? Datorită recursiei la coadă. Recursia la coadă este definită ca un apel recursiv exact la ieșirea din funcție. Toate exemplele pe care le-am dat la recursia bottom-up sînt recursive la coadă. Exemplele date la top-down nu sînt recursive la coadă, cu excepția lui cmmdc.

Recursia la coadă este foarte utilă, deoarece nu consumă stivă. În mod normal fiecare apel de funcție consumă cel puțin patru octeți pe stivă (adresa de întoarcere). Ei bine, în cazul apelurilor recursive la coadă stiva consumată este zero (ca să fim exacţi nu este zero, ci ''O(1)''). Explicația acestui fapt este prea tehnică pentru a o detalia aici. Ea ține de modul în care este organizat calculatorul modern Von Neumann și de modul în care se execută apelurile de funcții.

Ce înseamnă pentru noi acest lucru? Înseamnă că putem chema o funcție, recursiv, de un milion de ori, fără să depășim memoria stivă. Ce înseamnă pentru omenire acest lucru? Înseamnă că putem avea întregi limbaje care nu conțin instrucțiuni de ciclare (while sau for), cum ar fi limbajele funcționale (Scheme, Lisp) sau limbajele logice (Prolog). Acest lucru este posibil deoarece recursivitatea la coadă poate înlocui cu succes buclele. Aceste limbaje se bazează pe definiția recursivă a algoritmului. În unele cazuri programele sînt mai clare într-o gândire recursivă.

== Tema 8 ==

Să se rezolve următoarele probleme (program C trimis la [https://www.nerdarena.ro/ NerdArena]):

* [https://www.nerdarena.ro/problema/fibonacci Fibonacci]
* [https://www.nerdarena.ro/problema/primrec Primrec]
* [https://www.nerdarena.ro/problema/maxrec Maxrec]
* [https://www.nerdarena.ro/problema/factorizare Factorizare]
* [https://www.nerdarena.ro/problema/sumprim Sumprim]
* [https://www.nerdarena.ro/problema/fibrec Fibrec]
* [https://www.nerdarena.ro/problema/aparitii2 Aparitii2]


== Tema opțională ==

Să se rezolve următoarele probleme (program C trimis la [https://www.nerdarena.ro/ NerdArena]):

* [https://www.nerdarena.ro/problema/permutari1 Permutări1] Problema cere ca, dându-se indicii anumitor permutări să se calculeze suma acelor permutări.
* [https://www.nerdarena.ro/problema/aranjamente Aranjamente] Problema cere generarea eficientă a tuturor aranjamentelor și a calculului unor proprietăți ale lor.
* [https://www.nerdarena.ro/problema/optim Optim] dată la ONI 2012 clasa a 8-a, problemă ce se poate rezolva recursiv.
* [https://www.nerdarena.ro/problema/balance Balance] dată la Shumen 2012 juniori, problemă pentru avansați, deoarece ea necesită backtracking, ceea ce nu am predat.


'''Temă de gândire, opțională:''' Care ar fi un algoritm iterativ de rezolvare a turnurilor din Hanoi? Încercați să găsiți reguli simple, nu doar să mimați algoritmul recursiv folosind o stivă.


[http://solpedia.francu.com/wiki/index.php?title=Clasa_a_7-a_Lec%C8%9Bia_8:_Recursivitate_(2) Accesează rezolvarea temei 8]