Clasa a 7-a Lecția 8: Recursivitate (2)
Înregistrare video lecție
Exemple de funcții recursive
Iată câteva probleme care se rezolvă ușor cu funcții recursive:
Palindrom
Verificare palindrom:
#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;
}
Permutări
Dându-se n să se afișeze toate permutările mulțimii numerelor de la 1 la n în ordine lexicografică.
#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;
}
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 folosit[] se umple, vom plasa pe poziția curentă tot mai puține numere, dar le vom parcurge pe toate n. 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 v[]. Convenția este că dacă am ajuns la poziția poz am plasat deja poz elemente, iar cifrele rămase for fi în vector la pozițiile poz..n-1.
Vom scrie, la început, numerele de la 1 la n în vectorul v[]. Vrem să plasăm un element pe poziția poz. El va fi ales de pe o poziția i care se află după poz, i ≤ poz. Vom interschimba, deci, elementele aflate pe pozițiile poz și i. Aceasta îmi garantează că elementele rămase pe pozițiile poz+1..n-1 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 poz și i.
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:
#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;
}
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:
long long fact( int n ) {
if ( n == 1 )
return 1;
return n * fact( n - 1 );
}
Cel cu memoizare va folosi un vector ce va stoca elementele deja calculate:
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];
}
Fibonacci
Algoritmul direct de calcul al celui de-al n-lea termen al șirului lui Fibonacci:
int fib( int n ) {
if ( n == 1 || n == 2 )
return 1;
return fib( n-1 ) + fib( n-2 );
}
Cel cu memoizare va folosi un vector ce va stoca elementele deja calculate:
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
}
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:
| Top-down | Bottom-up |
|---|---|
#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;
}
|
#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;
}
|
Putere
Iată o comparație a celor două implementări ale funcției putere, implementată recursiv top-down și bottom-up cu acumulator:
| Top-down | Bottom-up |
|---|---|
#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;
}
|
#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;
}
|
CMMDC
De remarcat că funcția recursivă care calculează cmmdc a două numere, prezentată în lecția trecută, este deja bottom-up cu acumulator:
int cmmdc( int a, int b ) {
if ( b == 0 )
return a;
return cmmdc( b, a % b );
}
Fibonacci
Iată o comparație a celor două implementări ale șirului lui Fibonacci, implementat recursiv top-down și bottom-up cu acumulator:
| Top-down | Bottom-up |
|---|---|
int fib( int n ) {
if ( n == 1 )
return 0;
if ( n == 2 )
return 1;
return fib( n - 1 ) + fib ( n - 2 );
}
Ea va fi apelată astfel: f = fib( 15 );
Unde 15 este numărul termenului dorit. |
int fib( int n, int f1, int f2 ) {
if ( n == 1 )
return f1;
return fib( n - 1, f2, f1 + f2 );
}
Ea va fi apelată astfel: f = fib( 15, 0, 1 );
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:
| Top-down | Bottom-up |
|---|---|
int sumac( int n ) {
if ( n == 0 )
return 0;
return n % 10 + sumac( n / 10 );
}
Ea va fi apelată astfel: s = sumac( 2324103 );
Unde 2324103 este numărul căruia îi calculăm suma cifrelor. |
int sumac( int n, int suma ) {
if ( n == 0 )
return suma;
return sumac( n / 10, suma + n % 10 );
}
Ea va fi apelată astfel: s = sumac( 2324103, 0 );
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:
| Top-down | Bottom-up |
|---|---|
#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;
}
|
#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;
}
|
Interclasare vectori ordonați
De remarcat că interclasarea a doi vectori ordonați, prezentată data trecută, este bottom-up cu acumulator (vectorul v3[] 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 (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 );
}
}
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 n. 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:
| Top-down | Bottom-up |
|---|---|
#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;
}
|
#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;
}
|
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 NerdArena):
Tema opțională
Să se rezolve următoarele probleme (program C trimis la NerdArena):
- Permutări1 Problema cere ca, dându-se indicii anumitor permutări să se calculeze suma acelor permutări.
- Aranjamente Problema cere generarea eficientă a tuturor aranjamentelor și a calculului unor proprietăți ale lor.
- Optim dată la ONI 2012 clasa a 8-a, problemă ce se poate rezolva recursiv.
- 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ă.
