In questo articolo implementiamo il metodo delle potenze ricorsive in linguaggio C. Il nostro obiettivo è capire questo elegante metodo per la semplificazione del calcolo delle potenze e contestualmente rafforzare la comprensione delle funzioni ricorsive.
PREMESSA
Come sempre, prima di iniziare, facciamo alcune premesse.
L'operazione di elevamento a potenza base esp si esegue moltiplicando base per se stessa esp-1 volte (nel dubbio, si veda https://it.wikipedia.org/wiki/Potenza_(matematica) ); noi lavoreremo solo con valori interi e nei limiti dei valori esprimibili dal tipo int del linguaggio C (dipendente dal compilatore).
La libreria standard del C fornisce la funzione pow() (date un occhio qui http://www.cplusplus.com/reference/cmath/pow/ ) ma per il nostro studio dovremo ovviamente farne a meno!
CALCOLO TRADIZIONALE
L'algoritmo più semplice che possiamo progettare è quello presentato qui sotto:
int pot_tradizionale(int base, int esp)
{
int res = 1;
while (esp > 0)
{
res = res * base;
esp = esp - 1;
}
return res;
}
Credo che il codice sia di semplice comprensione e che non abbia perciò bisogno di particolari spiegazioni.
CALCOLO CON RICORSIONE
Se vogliamo trasformare la funzione precedente utilizzando la ricorsione dobbiamo pensare genericamente che
baseesp = base * base(esp-1)
e che per esp=1 ed esp=0 abbiamo i seguenti casi particolari:
base1 = base
base0 = 1
possiamo scrivere:
int pot_ricorsivo_semplice(int base, int esp)
{
if (esp == 0)
return 1;
if (esp == 1)
return base;
return base*pot_ricorsivo_semplice(base, esp-1);
}
Nel caso l'algoritmo risultasse di difficile comprensione suggerisco di inserire una printf() all'inizio della funzione per stampare i parametri base ed esp. Inoltre possiamo verificare il valore di ritorno di ciascuna chiamata: per questo dobbiamo avere un unico punto di uscita (un'unica return per intenderci) in cui visualizzare il risultato.
Qui sotto trovate la funzione opportunamente modificata:
int pot_ricorsivo_semplice(int base, int esp)
{
int res;
printf("base=%d esponente=%d\n", base, esp);
if (esp == 0)
res = 1;
else if (esp == 1)
res = base;
else
res = base*pot_ricorsivo_semplice(base, esp - 1);
printf("res=%d\n", res);
return res;
}
Eseguendola, ad esempio con base=3 ed esp=11 otterremo a video:
base=3 esponente=11
base=3 esponente=10
base=3 esponente=9
base=3 esponente=8
base=3 esponente=7
base=3 esponente=6
base=3 esponente=5
base=3 esponente=4
base=3 esponente=3
base=3 esponente=2
base=3 esponente=1
res=3
res=9
res=27
res=81
res=243
res=729
res=2187
res=6561
res=19683
res=59049
res=177147
Come atteso vengono eseguite 11 chiamate, ovvero 10 moltiplicazioni e uno step interno con esponente=1.
POTENZE RICORSIVE
Entrambi gli algoritmi precedenti non ottimizzano in alcun modo il numero di moltiplicazioni da eseguire: saranno sempre uguali al valore dell'esponente. Analizziamo ora il metodo delle potenze ricorsive il cui scopo è appunto ridurre il numero di moltiplicazioni.
Partiamo con un esempio che può aiutare a capire:
38 può essere calcolato con 7 moltiplicazioni, ovvero 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 = 6561
se però consideriamo che 38 = ((32)2)2 possiamo svolgere l'operazione con 3 sole moltiplicazioni
3 * 3 = 9
9 * 9 = 81
81 * 81 = 6561
Questo metodo ci permette di eseguire log2(esp) moltiplicazioni!
Naturalmente va considerato anche il caso in cui l'esponente non sia una potenza di 2, ad esempio:
310 = (35)2 = (3 * 34)2 = (3 * (32)2)2
si risolve con 4 moltiplicazioni
3 * 3 = 9
9 * 9 = 81
81 * 3 = 243
243 * 243 = 59049
Qui di seguito l'implementazione:
int pot_ricorsivo(int base, int esp)
{
if (esp == 0)
return 1;
if (esp == 1)
return base;
if (esp % 2) // se esp dispari
return base * pot_ricorsivo(base*base, esp / 2);
else // se esp pari
return pot_ricorsivo(base*base, esp / 2);
}
Per rendersi conto del funzionamento suggerisco anche qui di inserire una printf() all'inizio della funzione e di visualizzare il risultato di ciascuna chiamata, in modo da poter verificare la sequenza.
Qui sotto la funzione modificata:
int pot_ricorsivo(int base, int esp)
{
int res;
printf("base=%d esponente=%d\n", base, esp);
if (esp == 0)
res = 1;
else if (esp == 1)
res = base;
else
{
if (esp % 2) // se esp dispari
res = base * pot_ricorsivo(base*base, esp / 2);
else // se esp pari
res = pot_ricorsivo(base*base, esp / 2);
}
printf("res=%d\n", res);
return res;
}
Eseguendo questa funzione con base=3 ed esp=11, come nell'esempio precedente, otterremo a video:
base=3 esponente=11
base=9 esponente=5
base=81 esponente=2
base=6561 esponente=1
res=6561
res=6561
res=59049
res=177147
Come si può notare, rispetto all'algoritmo precedente abbiamo ridotto di molto il numero di chiamate (da 11 a 4), questo perchè siamo passati da una complessità O(n) ad una complessità O(log2(n)).
Una precisazione: le due chiamate interne restituiscono entrambe lo stesso valore (6561) perchè in effetti l'ultima chiamata (con esponente esp=1) non fa altro che restituire il valore già calcolato dal chiamante (base*base); si potrebbe rimuovere l'ultima chiamata gestendo anche il caso specifico per esp==2 ... eventualmente potete sperimentarlo come esercizio!
POTENZE RICORSIVE CON VERSIONE ITERATIVA
Per finire vediamo un'implementazione dell'algoritmo delle potenze ricorsive... senza ricorsione! In effetti il procedimento matematico alla base dell'idea non richiede automaticamente una traduzione in algoritmo ricorsivo; il metodo può essere implementato con una semplice iterazione.
Ecco qui il codice:
int pot_ricorsivo_con_ciclo(int base, int esp)
{
int pot = 1;
while (esp > 0)
{
if (esp % 2) // se esp dispari
{
pot = pot*base;
esp = esp - 1;
}
else // se esp pari
{
base = base*base;
esp = esp / 2;
}
}
return pot;
}
Sostanzialmente la funzione eleva al quadrato la base dimezzando l'esponente se questo è pari; se invece l'esponente è dispari, e lo sarà almeno una volta quando alla fine esp==1, moltiplica i vari fattori nella variabile pot.
Anche per questa funzione suggerisco di inserire delle printf(): il procedimento risulterà molto più chiaro!
CONCLUSIONI
Abbiamo visto come il metodo delle potenze ricorsive può ottimizzare il calcolo della potenza, passando da una complessità O(n) ad una complessità O(log2(n)) e abbiamo anche visto come questo possa essere ottenuto con un'implementazione iterativa, non ricorsiva.
In tutto questo abbiamo inoltre studiato il comportamento di una funzione ricorsiva inserendo delle printf() all'entrata e all'uscita della funzione, un metodo di debug forse rozzo per alcuni ma di sicura efficacia in questo caso!!!
