Funcții recursive pentru prelucarea cifrelor unui număr

Există numeroase probleme cu cifrele unui număr și multe dintre ele se pot rezolva cu ajutorul unei funcții – chiar recursive:

• suma cifrelor unui număr; suma cifrelor de unu numit tip (pare/impare, etc.);
• numărul de cifre; numărul de cifre de un anumit tip (pare/impare, etc.);
• construirea unui număr folosind anumite cifre din numărul dat;
• etc;

Pentru realizarea unei funcții recursive, care determină rezultatul cerut, folosim un algoritm de forma următoare:

• identificăm cazul particular;
• dacă suntem în cazul particular, obținem rezultatul în mod direct;
• dacă nu suntem în cazul particular:
• rezolvăm, prin autoapel, problema pentru numărul fără ultima cifră;
• cu rezultatul obținut și ultima cifră obținem rezultatul final, pentru numărul dat.

Desigur, algoritmul de mai sus trebuie adaptat la specificul problemei, dar în majoritatea situațiilor el este de acest tip!

Exemplu

Pentru a determina suma cifrelor unui număr procedăm astfel:

• antetul funcției va fi: int sumcif(int n)
• cazul particular poate fi când numărul este 0 (n==0). În acest caz rezultatul este 0;
• dacă n>0, determinăm rezultatul pentru numărul fără ultima cifră: S = sumcif(n/10);
• rezultatul final va fi S + n % 10 – suma cifrelor numărului fără ultima cifră, adunată cu ultima cifră a lui n.

Puse împreună, obținem:

int sumcif(int n)
{
    if(n == 0)
        return 0;
    else
    {
        int S = sumcif(n/10);
        return S + n%10;
    }
}