Funzioni ricorsive
La ricorsione
Le funzioni ricorsive sono una classe di funzioni che prevedono nella loro definizione la chiamata a se stesse. L’obiettivo di queste funzioni è quello di semplificare o suddividere il set di informazioni ricevute come parametro e applicare la stessa funzione ai set suddivisi o semplificati. Questa tecnica viene chiamata ricorsione. Gli algoritmi che utilizzano questa tecnica vengono chiamati ricorsivi.
Questo tipo di funzioni vengono definite suddividendo l’esecuzione della funzione in due macro casi:
1) caso base: se il valore di input rispetta determinati requisiti, allora la funzione svolge il suo compito e restituisce quando previsto un risultato;
2) caso generale: se non rispetta i suddetti requisiti, la funzione chiama se stessa con parametri eventualmente ed opportunamente modificati.
Le funzioni di questo tipo hanno quindi un comportamento simile a quello di un ciclo, in cui la funzione viene continuamente richiamata fino a quando non si arriva al caso base, che come visto sopra non richiama la funzione. A questo punto si torna indietro, e viene via via completata l’esecuzione delle funzioni chiamanti.
Nel diagramma sottostante uno schema di funzionamento generale di una funzione che chiama se stessa più volte fino ad arrivare ad un caso base.
Ambiti di applicazione
Gli algoritmi ricorsivi offrono in generale una soluzione più sintetica ed elegante a problemi che prevedono cicli, in quanto spesso non richiedono di usare variabili per gestire contatori o indici, inoltre separano bene la condizione di terminazione del ciclo (cioè il caso base) dal ciclo stesso (cioè caso generale).
La loro principale limitazione in C++ è che siccome le funzioni usano lo stack, un numero elevato di chiamate ricorsive a funzione va a riempirlo con un rischio di errore di “stack overflow”. Inoltre la creazione di una funzione (e la relativa distruzione) richiede tempo macchina col risultato di peggiorare le prestazioni (rispetto alla soluzione iterativa).
Quindi in generale le funzioni ricorsive non sono usate per gestire cicli su grandi moli di dati o dove le prestazioni sono critiche. Tuttavia siccome questo è un limite di natura tecnica, con l’utilizzo di computer e memorie sempre più grandi questo problema si è complessivamente ridotto col tempo.
Fattoriale
Come noto, la funzione f(x) = n! detta anche “fattoriale di n” è definita come
f(x) = n*n-1*n-2*…*1 = n!
Essa è cioè il prodotto di tutti gli interi che vanno da 1 a n. Essa può essere definita in modo ricorsivo in quanto è n! = n*(n-1)!
| Input | Funzione | |
| x=1 | f(x)=1 | Caso base |
| x>1 | f(x)=x * f(x-1) | Caso generale |
Proviamo a svolgere i passaggi per x = 5:
| Input | Esecuzione allo step | Valore calcolato |
| 5 | f(5)= 5* f(4) | 5 * f(4) |
| 4 | f(4)= 4* f(3) | 5 * (4 * f(3)) |
| 3 | f(3)= 3* f(2) | 5 * (4 * (3 * f(2)) |
| 2 | f(2)= 2* f(1) | 5 * (4 * (3 * (2 * f(1))) |
| 1 | f(1)= 1 | 5 * (4 * (3 * (2 * 1))) |
Come si vede dallo svolgimento la funzione è chiama se stessa con un parametro che decresce di 1 fino a quando non si arriva al caso base (1).
Qui una rappresentazione grafica. Si noti che in questo esempio tutte le funzioni sono deterministiche.
#include <iostream>
using namespace std;
int f(int n) {
if (n==1) {
return 1;
} else {
return n * f(n-1);
}
}
int main() {
int n;
cout << “Inserisci un valore n: “;
cin >> n;
int fact = f(n);
cout << “Il fattoriale è: “ << fact;
return 0;
}Numeri di Fibonacci
Come noto, la serie di Fibonacci è definita dalla seguente funzione generativa:
f(1) -> 1
f(2) -> 2
f(n) -> f(n-1) + f(n-2)
In questo caso quindi la funzione ricorsiva è funzione di due chiamate ricorsive sommate tra loro.
Proviamo a svolgerla per n=5:
| Input | Esecuzione allo step | Valore finale |
| 5 | f(5)= f(4) + f(3) | f(4) + f(3) |
| 4 | f(4)= f(3) + f(2) | (f(3) + f(2)) + f(3) |
| 3 | f(3)= f(2) + f(1) | ((f(2) + f(1)) + f(2)) + (f(2) + f(1)) |
| 2 | f(2)= 1 | ((1 + 1) + 1) + (1 + 1) |
| 1 | f(1)= 1 | 5 |
Qui una rappresentazione grafica.
In C++ (si omette il main):
int fibo(int n) {
if (n==1) {
return 1;
};
if (n==2) {
return 1;
}
return fibo(n-1) + fibo(n-2);
}Analogamente si può procedere per la generazione di qualsiasi serie. Si può osservare che anche questa funzione è deterministica.
Verifica di un numero primo
La funzione ricorsiva riceve come parametri il numero da verificare e un divisore e restituisce un valore booleano (true se primo, false se non primo).
Essa ha dunque la seguente firma:
bool f(int numero, int divisore)
In questo caso quindi è funzione di due parametri, e la ricorsione avviene variando uno di essi (l’altro è costante).
La possiamo implementare nel seguente modo:
| Numero | Condizioni | Risultato |
| 1 | n % d != 0 | f(n, d-1) |
| 2 | n % d == 0 | False |
| 3 | d == 1 | True |
| 4 | n == 1 | True |
Vediamo in dettaglio come funziona:
- La condizione 1 è quella generale, ovvero quella in cui n non è divisibile per d, in questo caso viene eseguita la funzione passando n e d-1;
- La condizione 2 è quella in cui n è divisibile per d, quindi l’esecuzione si ferma perché il numero non è primo;
- La condizione 3 è il punto di arrivo se la condizione 2 non viene mai soddisfatta;
- La condizione 4 è il caso in cui n ha un valore pari ad 1;
- La funzione viene chiamata la prima volta con il massimo divisore possibile, cioè n-1;
- Anche in questo caso la funzione è deterministica.
Proviamo a vedere un esempio con n => 5 e d = (n-1) => 4. Il risultato atteso è true.
| Input (n, d) | Esecuzione allo step |
| (5,4) | f(5,4)= f(5,3) |
| (5,3) | f(5,3)= f(5,2) |
| (5,2) | f(5,2)= f(5,1 |
| (5,1) | f(5,1)= true |
Graficamente:
Ora un esempio con n=10 che restituisce false.
| Input (n, d) | Esecuzione allo step |
| (10,9) | f(10,9)= f(10,8) |
| (10,8) | f(10,8)= f(10,7) |
| (10,7) | f(10,7)= f(10,6) |
| (10,6) | f(10,6)= f(10,5) |
| (10,5) | f(10,5)= false |
Graficamente:
In codice C++:
bool isPrime(int n, int d) {
if (d == 1) {
return true;
}
if (n % d == 0) {
return false;
} else {
return isPrime(n, d-1);
}
}Fibonacci con array
In questo caso viene richiesto di generare un array contenente tutti i primi n numeri di Fibonacci.
Siccome in C++ per modificare un array questo deve essere passato come parametro, possiamo definire la funzione con la seguente firma:
void f(int i, int a[])
Dove i è il numero i-esimo della serie di Fibonacci e a è l’array [x1, x2, …, xn]) dove inseriremo i valori.
La funzione non è deterministica in quanto non viene restituito un valore ma viene modificato lo stesso array.
La sua implementazione è la seguente:
| Funzione | Condizioni | Azione |
| f(i,a) | i<2 | a[0]=1; a[1]=1 |
| f(i,a) | i>=2 | f(i-1, a);a[i]=a[i-1]+a[i-2] |
In dettaglio:
- Per i<2 (quindi 1 o 0): è il caso base;
- Per i>=2: è il caso generale. Qui la funzione prima genera i valori precedenti nell’array e poi genera quello attuale.
Vediamo un esempio di esecuzione con n=5 e a[] con 5 elementi.
| Input | Esecuzione |
| f(5, a) | f(4, a); a[4]=a[3]+a[2] |
| f(4, a) | f(3, a);a[3]=a[2]+a[1] |
| f(3, a) | f(2, a);a[2]=a[2]+a[1] |
| f(2, a) | a[0]=1; a[1]=1; |
Graficamente:
Codice C++:
#include <iostream>
using namespace std;
void fibo(int i, int result[]) {
if (i<2) {
result[0]=1;
result[1]=1;
} else {
fibo(i-1, result);
result[i]=result[i-1]+result[i-2];
}
}
int main()
{
int n;
cout<<"Inserisci n:";
cin >> n;
int list[n];
fibo(n-1, list);
for (int i=0; i<n; i++) {
cout << list[i] << " ";
}
return 0;
}