SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Recursivitate · lecția 4

Recursivitate (2): pe vectori, pe șiruri și algoritmul de umplere (fill)

60 minmate-info

Înainte de lecția asta: XI.3 Recursivitate (1): mecanism, stivă, funcții recursive simple, X.8 Tablouri bidimensionale (matrice): declarare, parcurgere pe linii și coloane

Ce vei ști după lecție

  • Scrii funcții recursive care parcurg un vector (sumă, maxim, căutare, afișare inversă).
  • Scrii funcții recursive pe șiruri de caractere.
  • Folosești algoritmul de umplere (fill) pe matrice: zone, insule, labirinturi.
  • Ști să alegi parametrii potriviți pentru apelul recursiv (indice, lungime).

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 4 din 21 · mai sunt 17Urmează: XI.5 · Metoda Divide et Impera: MergeSort, QuickSort, căutare binară recursivăVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Recursivitate pe vectori

Același gând ca la numere: „suma vectorului de n elemente = suma primelor n − 1 elemente + ultimul”. Problema se micșorează cu un element la fiecare apel.

Suma recursivă

#include <iostream>
using namespace std;

int a[101], n;

int suma(int a[], int n)               // suma a[1..n]
{
    if (n == 0) return 0;                  // caz de bază: vectorul vid
    return suma(a, n - 1) + a[n];
}

int maxim(int a[], int n)              // maximul din a[1..n]
{
    if (n == 1) return a[1];               // un singur element
    int m = maxim(a, n - 1);
    return (a[n] > m) ? a[n] : m;
}

bool apare(int a[], int n, int x)      // există x în a[1..n]?
{
    if (n == 0) return false;
    if (a[n] == x) return true;
    return apare(a, n - 1, x);
}

int main()
{
    int x;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> x;
    cout << suma(a, n) << ' ' << maxim(a, n) << ' ' << (apare(a, n, x) ? "DA" : "NU");
    return 0;
}

De ce așa?

De ce maxim are cazul de bază n == 1 și nu n == 0? Maximul unui vector fără elemente nu există. Cel mai mic vector pentru care răspunsul are sens are un element, iar atunci maximul este chiar a[1]. De ce apare poate să se oprească înainte de caz de bază? Dacă a[n] == x, răspunsul este deja „da”; nu mai căutăm în rest.

Urmărire pentru suma(a, 4) cu a = (4, 7, 1, 8):

apel n a[n] returnează
suma(a, 4) 4 8 suma(a, 3) + 8 = 12 + 8 = 20
suma(a, 3) 3 1 suma(a, 2) + 1 = 11 + 1 = 12
suma(a, 2) 2 7 suma(a, 1) + 7 = 4 + 7 = 11
suma(a, 1) 1 4 suma(a, 0) + 4 = 0 + 4 = 4
suma(a, 0) 0

Intrare / ieșire

Intrare Ieșire
5
4 7 1 8 3
8
23 8 DA
5
4 7 1 8 3
9
23 8 NU

Afișare în ordine directă și inversă

Ca la cifre: cout înainte de apel dă ordinea directă, după apel dă ordinea inversă.

#include <iostream>
using namespace std;

int a[101], n;

void afisare(int a[], int i, int n)            // afișează a[i..n]
{
    if (i > n) return;
    cout << a[i] << ' ';                       // înainte de apel: ordine directă
    afisare(a, i + 1, n);
}

void afisareInversa(int a[], int i, int n)
{
    if (i > n) return;
    afisareInversa(a, i + 1, n);
    cout << a[i] << ' ';                       // după apel: ordine inversă
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    afisare(a, 1, n);
    cout << '\n';
    afisareInversa(a, 1, n);
    return 0;
}

De ce așa?

De ce aici recursivitatea merge pe indice (i + 1) și la sumă pe lungime (n − 1)? Sunt două moduri de a micșora problema: fie scoatem ultimul element (rămâne a[1..n−1]), fie ne mutăm începutul (rămâne a[i+1..n]). Alegem modul care face codul mai simplu pentru problema respectivă.

2. Recursivitate pe șiruri de caractere

#include <iostream>
#include <cstring>
using namespace std;

char s[256];

int nrVocale(char s[], int i)             // vocalele din s[i...]
{
    if (s[i] == '\0') return 0;                              // am ajuns la terminator
    return (strchr("aeiou", s[i]) != NULL) + nrVocale(s, i + 1);
}

int main()
{
    cin >> s;
    cout << nrVocale(s, 0);
    return 0;
}

De ce așa?

De ce verificăm s[i] == '\0' înaintea lui strchr? strchr("aeiou", '\0') nu returnează NULL (terminatorul face parte din șir) și am număra o „vocală” în plus (am spus asta și la lecția X.11).

3. Algoritmul de umplere (fill)

Avem o hartă (matrice) cu 1 = pământ și 0 = apă. Câte insule sunt (zone de 1 vecine pe orizontală sau verticală)? Care este cea mai mare?

Harta

Ideea. Când găsim un 1 nevizitat, am descoperit o insulă nouă. O „scufundăm” complet (marcăm toate celulele ei) cu o funcție recursivă care se extinde către cei 4 vecini.

Pașii

#include <iostream>
using namespace std;

int a[102][102], n, m;

int fill(int i, int j)                              // întoarce aria insulei care conține (i, j)
{
    if (i < 1 || i > n || j < 1 || j > m) return 0; // în afara hărții
    if (a[i][j] != 1) return 0;                     // apă sau deja vizitat
    a[i][j] = 2;                                    // marcăm ca vizitat, ÎNAINTE de apeluri
    return 1 + fill(i - 1, j) + fill(i + 1, j) + fill(i, j - 1) + fill(i, j + 1);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    int insule = 0, amax = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 1)                       // insulă nouă
            {
                insule++;
                int aria = fill(i, j);
                if (aria > amax) amax = aria;
            }
    cout << insule << ' ' << amax;
    return 0;
}

De ce așa?

De ce marcăm a[i][j] = 2 înainte de apelurile recursive? Dacă nu am marca, fill(1, 1) ar apela fill(2, 1), care ar apela înapoi fill(1, 1) (vecinul de sus), și tot așa la infinit. Marcarea spune „aici am fost deja”. De ce verificăm mai întâi dacă (i, j) e în hartă? Altfel am citi a[0][j] sau a[n+1][j], în afara matricei date. De ce 1 + suma celor 4 apeluri? Celula curentă contribuie cu 1 la arie, iar fiecare vecin adaugă aria părții de insulă pe care o descoperă el.

Urmărire (harta din figură, parcurgere pe linii):

celulă (i, j) valoare acțiune insule arie
(1, 1) 1 insulă nouă; fill marchează (1,1), (2,1), (1,2) 1 3
(1, 2) 2 deja vizitat 1
(2, 4) 1 insulă nouă: (2,4), (2,5), (3,4) 2 3
(4, 1) 1 insulă nouă: (4,1), (5,1), (5,2) 3 3
(5, 5) 1 insulă nouă: doar (5,5) 4 1

La final: 4 insule, aria maximă 3.

Intrare / ieșire

Intrare Ieșire
harta din figură (5 × 5) 4 3
1 1
1
1 1

Variante care se rezolvă la fel:

  • 8 vecini (și pe diagonală): încă 4 apeluri, cu (i ± 1, j ± 1);
  • labirint: există drum de la start la ieșire? Pornești fill din start și verifici dacă ieșirea a fost marcată;
  • numărul de camere într-un plan de clădire (ziduri = 1, spațiu liber = 0).

Capcană

Pentru hărți foarte mari (de exemplu 1000 × 1000), recursivitatea poate umple stiva: o insulă de 10⁶ celule înseamnă 10⁶ cadre imbricate. Atunci se folosește o coadă (algoritmul lui Lee, lecția XI.17) sau o stivă proprie.

4. Greșeli frecvente

Greșeala Efect Corect
nu marchezi celula înainte de apeluri recursie infinită a[i][j] = 2; mai întâi
verifici a[i][j] înainte de a verifica marginile citire în afara matricei întâi i, j în hartă
maxim cu caz de bază n == 0 și return a[0] valoare irelevantă caz de bază n == 1
suma(a, n - 1) + a[n - 1] pentru vector indexat de la 1 element greșit potrivește indexarea
uiți să resetezi harta între teste rezultate amestecate citește harta din nou
strchr(..., s[i]) fără oprire la '\0' o vocală în plus verifică întâi terminatorul

5. La BAC

La BAC

Subiectul I: subprograme recursive cu vectori (f(st, dr, v), f(v, n)): „ce valoare întoarce apelul?” Se rezolvă cu tabelul apelurilor. Subiectul II/III: fill apare rar la Bac, dar este frecvent la olimpiadă; ideea de „marcare ca vizitat” se regăsește la parcurgerea grafurilor (XI.11).

6. Exersează pe hârtie

Răspunsurile sunt la final: încearcă întâi singur.

1. Pentru a = (2, 5, 1), scrie apelurile și valoarea lui suma(a, 3).

2. Care este valoarea lui maxim(a, 4) pentru a = (3, 9, 2, 7)? Scrie apelurile.

3. Ce afișează afisareInversa(a, 1, 3) pentru a = (5, 6, 7)?

4. Scrie o funcție recursivă bool palindrom(char s[], int st, int dr).

5. Scrie o funcție recursivă care returnează numărul de elemente pare dintr-un vector.

6. Pe harta 1 0 1 / 0 1 0 / 1 0 1, câte insule sunt cu 4 vecini? Dar cu 8 vecini?

7. De ce în fill marcăm a[i][j] = 2 înainte de apelurile recursive?

8. Câte apeluri ale lui fill se fac pentru o insulă formată dintr-o singură celulă (inclusiv primul)?

9. (BAC) Ce întoarce f(1, 5, v) pentru v = (3, 8, 1, 9, 4) (indexat de la 1)?

int f(int st, int dr, int v[]) { if (st == dr) return v[st]; int m = f(st + 1, dr, v); return v[st] > m ? v[st] : m; }

7. Mai departe (pentru cine vrea mai mult)

Flood fill în programe de desen. Unealta „găleată de vopsea” din orice editor de imagini este exact fill: pornește de la pixelul pe care ai dat clic și colorează toți pixelii vecini de aceeași culoare.

Număr de insule pe hărți reale. Problema „Number of Islands” este una dintre cele mai frecvente la interviurile de angajare în IT. Variantele ei: insule cu 8 vecini, insulă maximă, „lacuri” (apă înconjurată de pământ).

Backtracking pe matrice. Dacă la fill nu marchezi definitiv ci „demarchezi” la întoarcere, obții căutarea tuturor drumurilor dintr-un labirint: un exemplu de backtracking (lecțiile XI.6–XI.8).

De la recursivitate la stivă proprie. Orice funcție recursivă poate fi scrisă iterativ cu o stivă pe care o gestionezi singur (lecția XI.17). Așa se evită depășirea stivei la date mari.

Rezumat

  • Pe vectori: recursie pe lungime (n − 1) sau pe indice (i + 1); cazul de bază: vector vid sau cu un element.
  • Ordinea afișării: înainte de apel = directă, după apel = inversă.
  • Fill: marchezi celula, apelezi pentru vecini, te oprești la margine sau la celule deja vizitate/apă.
  • Aria unei zone: 1 + suma apelurilor pentru vecini.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 100 min

Recursivitate: stiva de apeluri, cifre, vectori, fill

  • Urmărești pe stivă orice funcție recursivă și spui exact ce afișează sau ce returnează (grila de la Subiectul I).
  • Repari funcțiile recursive greșite: caz de bază, apel care nu se apropie, parametru prin valoare în loc de referință.
  • Scrii recursiv prelucrări pe cifre, pe vectori și algoritmul de umplere (fill).

Fișa acoperă și: XI.3

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • afisarevectorrec#835

    ușoară
  • afisarevectorrec1#836

    ușoară
  • fsumvecrec#1843

    ușoară
  • fill#837

    Prima problemă de umplere: numărul de zone.

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • fsumrec#938

    ușoară
  • nr-aparitii-rec#1752

    ușoară
  • nrvocrec#1654

    ușoară
  • puteri2#843

    ușoară
  • puteri3#872

    ușoară
  • fcautarerec#1511

    ușoară
  • croco#840

    Fill + cea mai mare zonă.

    medie

Pentru cei care vor mai mult

  • iesire#838

    medie
  • grupuri#1507

    ușoară

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. suma(a, 3) = suma(a, 2) + 1; suma(a, 2) = suma(a, 1) + 5; suma(a, 1) = suma(a, 0) + 2 = 2. Deci suma(a, 2) = 7, iar suma(a, 3) = 8.

2. maxim(a, 1) = 3; maxim(a, 2) = 9; maxim(a, 3) = 9; maxim(a, 4) compară a[4] = 7 cu 9 și returnează 9.

3. 7 6 5.

4.

#include <iostream>
#include <cstring>
using namespace std;

char s[256];

bool palindrom(char s[], int st, int dr)
{
    if (st >= dr) return true;                  // 0 sau 1 caractere: palindrom
    if (s[st] != s[dr]) return false;
    return palindrom(s, st + 1, dr - 1);
}

int main()
{
    cin >> s;
    cout << (palindrom(s, 0, strlen(s) - 1) ? "DA" : "NU");
    return 0;
}

5.

#include <iostream>
using namespace std;

int a[101], n;

int nrPare(int a[], int n)
{
    if (n == 0) return 0;
    return (a[n] % 2 == 0) + nrPare(a, n - 1);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << nrPare(a, n);
    return 0;
}

6. Cu 4 vecini: 5 insule (fiecare 1 e izolat pe orizontală/verticală). Cu 8 vecini: 1 insulă (toate cele cinci celule se leagă prin diagonale de celula din centru).

7. Fără marcare, două celule vecine s-ar apela una pe alta la nesfârșit (fill(1, 1) → fill(2, 1) → fill(1, 1) …) și stiva s-ar umple.

8. 5 apeluri: cel inițial (care marchează celula) și 4 pentru vecini, toate întorcându-se imediat (fie sunt în afara hărții, fie au valoarea 0).

9. 9: funcția întoarce maximul din v[st..dr]. f(5,5) = 4; f(4,5) = 9; f(3,5) = 9; f(2,5) = 9; f(1,5): v[1] = 3 < 9 → 9.