Recursivitate la BAC: numărarea cifrelor pare

Numărarea recursivă a cifrelor pare descompune problema în două părți: ultima cifră și numărul rămas după eliminarea ei. La BAC, relația de recurență trebuie însoțită de un caz de bază corect. Cazul zero este important, deoarece cifra zero este pară și face parte din scrierea numărului zero.

Lecția este pentru conținuturile de recursivitate de la matematică-informatică. Funcția primește un număr natural de cel mult un miliard și returnează numărul cifrelor pare din reprezentarea lui zecimală obișnuită. Exersează apoi formularea aceleiași relații într-un subiect de BAC, păstrând domeniul și convențiile cerute acolo.

O cifră sau mai multe cifre

Un număr natural mai mic decât zece are o singură cifră. Pentru el, răspunsul este unu dacă cifra este pară și zero dacă este impară. Această regulă include explicit numărul zero.

Pentru un număr cu cel puțin două cifre, ultima cifră se obține prin rest la zece. Numărul rămas se obține prin împărțire întreagă la zece. Cifrele acestui număr rămas sunt exact cele dinaintea ultimei cifre.

Prin urmare, rezultatul este numărul cifrelor pare din partea rămasă plus contribuția ultimei cifre. Contribuția este unu pentru o cifră pară și zero pentru o cifră impară.

Relația recursivă în cuvinte

Pentru o singură cifră, răspunzi direct. Pentru mai multe cifre, ceri funcției să rezolve problema mai mică și adaugi informația despre ultima cifră. Nu reiei întreaga numărare de la început și nu ai nevoie de o variabilă globală.

Fiecare apel trebuie să returneze un rezultat complet pentru argumentul său. Apelul exterior îl folosește ca parte a propriului rezultat. Acest contract face funcția ușor de testat separat și evită dependența de apeluri anterioare.

Situație	Rezultat
Număr cu o singură cifră pară	1
Număr cu o singură cifră impară	0
Număr cu mai multe cifre	Rezultatul pentru partea rămasă plus contribuția ultimei cifre

Program C++ complet

Programul citește un singur număr natural și afișează rezultatul funcției. Parametrul este transmis prin valoare. Fiecare apel păstrează propria copie și se întoarce cu un întreg care reprezintă un număr de cifre.

#include <iostream>
using namespace std;

int numaraPare(long long n) {
    if (n < 10)
        return n % 2 == 0 ? 1 : 0;
    int ultima = int(n % 10);
    int contributie = ultima % 2 == 0 ? 1 : 0;
    return numaraPare(n / 10) + contributie;
}

int main() {
    long long n;
    cin >> n;
    cout << numaraPare(n);
    return 0;
}

Instrucțiunea de returnare din cazul de bază încheie acel apel. Pentru un număr cu mai multe cifre, apelul recursiv primește o valoare cu o cifră mai puțin, deci problema se micșorează până când ajunge la bază.

Exemplu: cifre pare, impare și zero

Pentru numărul douăzeci de mii patruzeci și șapte, ultima cifră este șapte și contribuția ei este zero. Funcția cere apoi rezultatul pentru două mii patru. Ultima cifră a acestuia este patru, deci contribuția este unu.

Apelurile urmează traseul 20047 → 2004 → 200 → 20 → 2. Fiecare pas elimină exact ultima cifră, iar cele două zerouri interioare ajung pe rând în poziția ultimei cifre. Scrierea numerică a argumentelor face traseul mai ușor de urmărit decât simpla enumerare verbală.

Argument	Contribuția ultimei cifre	Rezultat returnat
2	1, caz de bază	1
20	1	2
200	1	3
2004	1	4
20047	0	4

Tabelul este ordonat după revenire, de la problema cea mai mică spre cea inițială. Numărul are cifrele doi, zero, zero, patru și șapte; primele patru sunt pare, deci răspunsul este patru.

De ce baza cu o singură cifră este convenabilă

Dacă ai opri recursivitatea numai la zero și ai returna zero acolo, un apel direct pentru numărul zero ar produce un rezultat greșit pentru convenția noastră. Ar spune că numărul nu are cifre pare, deși scrierea lui conține cifra zero.

Ai putea trata intrarea zero separat în programul principal, dar baza cu o singură cifră include natural acest caz. Funcția rămâne corectă pentru întregul domeniu declarat, indiferent de locul din care este apelată.

Nu adăuga însă o contribuție suplimentară pentru zero după ce ai ajuns deja la o singură cifră. Cazul de bază reprezintă chiar cifra rămasă și trebuie numărat o singură dată.

Număr de cifre și sumă de cifre

Funcția adaugă unu pentru fiecare cifră pară, nu valoarea cifrei. Pentru numărul două sute patruzeci și șase, răspunsul este trei, nu doisprezece. Proprietatea de selecție este aceeași, dar acumulatorul exprimă altă mărime.

Dacă s-ar cere suma cifrelor pare, contribuția ar fi chiar cifra pară sau zero pentru o cifră impară. Cazul de bază ar trebui modificat în același sens. Schimbarea doar a pasului general ar produce o funcție inconsistentă.

Pentru produs, alegerea elementului neutru și tratarea absenței cifrelor eligibile ar cere o analiză separată. Nu înlocui mecanic adunarea cu înmulțirea fără să redefinești ce returnează fiecare apel.

Recursivitate fără variabile globale

O variabilă globală de numărare ar putea păstra accidental rezultatul de la un apel anterior. Ar trebui resetată la momentul potrivit, iar funcția ar depinde de starea externă. Varianta prezentată returnează direct rezultatul și nu are această dependență.

Poți apela funcția pentru mai multe numere, iar fiecare rezultat este calculat independent. Programul principal poate apoi însuma rezultate, selecta valori sau compara numărul cifrelor pare cu o limită.

Această separare între calculul unei proprietăți și folosirea rezultatului sprijină învățarea prin înțelegere. Funcția are o promisiune simplă: pentru argumentul primit, întoarce exact numărul cerut.

Adâncime, timp și memorie

Pentru un număr cu d cifre, funcția creează d apeluri, deoarece se oprește la o singură cifră. Fiecare nivel face un număr constant de operații, deci timpul este proporțional cu numărul cifrelor.

Memoria suplimentară este tot proporțională cu numărul cifrelor, prin stiva apelurilor. O variantă iterativă poate folosi memorie auxiliară constantă. Cele două rezolvă aceeași problemă, dar organizează diferit informația intermediară.

Nu confunda valoarea numărului cu numărul cifrelor sale. Un număr de ordinul unui miliard are doar zece cifre zecimale. În domeniul declarat, adâncimea este mică, iar demonstrația generală rămâne aceeași.

Exerciții cu răspunsuri

Numărul este zero. Rezultatul este unu, deoarece singura cifră este pară.

Numărul este 13579. Rezultatul este zero. Fiecare contribuție este zero, inclusiv cea din cazul de bază.

Numărul este 102030. Rezultatul este patru: trei cifre zero și cifra doi. Cifrele unu și trei sunt impare.

Numărul este 8888. Rezultatul este patru. Funcția numără aparițiile, nu cifrele distincte.

Întrebări frecvente

De ce nu returnez imediat contribuția ultimei cifre?

Pentru un număr cu mai multe cifre, aceasta ar ignora restul numărului. Rezultatul complet include și valoarea returnată de apelul pentru partea rămasă.

Pot folosi aceeași funcție pentru numere negative?

Nu în contractul prezentat. Domeniul este cel al numerelor naturale. Extinderea cere definirea modului în care tratezi semnul și valorile-limită ale tipului.

Cum verific o recurență proprie?

Testează separat baza și un număr cu două cifre, apoi urmărește revenirea pentru un exemplu mai lung. Pentru o analiză a funcției tale, poți consulta un profesor de informatică.