La soluzione di un problema si dice ricorsiva quando è espressa in termini di se stessa su un sottoinsieme dei dati da elaborare, considerando il caso particolare del sottoinsieme di dimensioni minime a cui si può applicare il procedimento risolutivo.
Una funzione, quindi è ricorsiva quando richiama se stessa.
È fondamentale assicurare la terminazione della chiamata ricorsiva della funzione introducendo il test a cui arrestare la chiamata di funzione.
La chiamata ricorsiva di una funzione comporta un intenso uso dello stack di sistema su cui vengono depositati gli indirizzi di ritorno e i parametri passati, quindi potrebbe essere più conveniente ricorrere ad un procedimento iterativo. Comunque un algoritmo ricorsivo, a volte, viene preferito perchè descrive in forma compatta e semplice il procedimento risolutivo di un problema.
Sia dato un elenco di numeri da sommare. Il procedimento risolutivo si può esprimere nella forma:
Il programma in linguaggio C che realizza la somma mediante la ricorsione richiede che venga dichiarato il puntatore all'array di elementi da sommare:
long x[];
Acquisire da file l'elenco dei valori da sommare.
la dichiarazione della funzione somma che riproduce il comportamento espresso nella formulazione ricorsiva è:
long somma(int n) {
if (n==0) return x[0];
else return somma(n-1) + x[n];
}
in cui il parametro n è il numero di valori contenuti nell'elenco meno 1, quindi si riferisce all'indice dell'ultimo elemento nell'array.
il test sul raggiungimento della quantità 1 di elementi da sommare assicura che le chiamate ricorsive si fermeranno.
Finchè c'è più di un elemento da sommare viene chiamata nuovamente la stessa funzione, però chiedendo di aggiungere all'elemento in posizione n la somma degli elementi che lo precedono.
Nel main si provvederà ad inizializzare l'array degli elementi da sommare, prelevando i valori fa un file, quindi si avvia la somma chiamando la funzione Somma:
int main(int argc, char *argv[]) {
. . .
printf("%ld", somma(9));
. . .
}
in cui si è supposto che si debbano sommare 10 elementi.
L'elevazione alla potenza n di un numero b corrisponde a moltiplicare la base b per se stessa n volte:
| bn = | b · b · ... · b |
| ← n volte → |
con b ≠ 0
In termini ricorsivi la potenza n-ma del numero b si esprime nella forma seguente:
Potenza (b, n)
Se n è uguale a 0 (e b≠0) allora la potenza è 1,
Altrimenti:
Moltiplicare b per la Potenza (b, n-1).
La dichiarazione della funzione Potenza che riproduce il comportamento ricorsivo è la seguente:
int potenza(long base, int esponente) {
if (esponente==0) return 1;
else return potenza(base, esponente-1)*base;
}
Nel main() la chiamata della funzione Potenza avviene passando i valori dei parametri base ed esponente:
int main(int argc, char *argv[]) {
. . .
printf("%ld", Potenza(3L, 4));
. . .
}
Si consideri un numero naturale n. Un numero i>1 e che sia anche i<n/2 è un divisore di n se fornisce resto uguale a zero.
Tale divisore e il quoziente rappresentano i fattori del numero n:
n = quoziente · i.
A questi due fattori si applica ricorsivamente lo stesso procedimento, fino a quando si trova un divisore = n, ma n≠1.
Scomporre (n)
determinare un divisore, e il relativo quoziente, di n,
se il divisore è diverso sia da 1 che da n
allora {
scomporre il divisore
scomporre il quoziente
}
Altrimenti
se il dividendo n è diverso da 1
allora n è un fattore primo.
La funzione che scompone il numero n in due fattori è la seguente:
void scomponi (int n) {
int i, quoziente, resto;
i=1;
do {
++i;
quoziente = n/i;
resto = n % i;
} while (resto!=0);
if (i!=n) {
scomponi(quoziente);
scomponi(i);
} else {
if (n!=1) printf("%d un fattore primo\n", n);
}
}
Un esempio di comportamento dell'algoritmo ricorsivo applicato al numero 30:
Scomporre (30):
si trova quoziente=15 e divisore=2
Scomporre (2):
2 è un fattore primo.
Scomporre (15):
Si trova quoziente=5 e divisore=3
Scomporre (5):
5 è un fattore primo.
Scomporre (3):
3 è un fattore primo.
Dati i due numeri, l'algoritmo di Euclide consiste nel calcolare il resto della divisione tra m ed n, Se il resto è zero, allora il massimo comun divisore è n altrimenti il procedimento si ripete prendendo il resto della divisione tra il quoziente ed il resto ottenuti prima.
In termini ricorsivi il procedimento si descrive:
calcola il Massimo Comun Divisore tra m ed n:
Se m è uguale ad n allora n è il Massimo Comun Divisore
altrimenti
se m>n calcola il Massimo Comun Divisore tra m-n e n
altrimenti calcola il Massimo Comun Divisore tra m e n-m
La funzione in linguaggio C che realizza l'algoritmo è:
int MCD(int m, int n) {
if (m==n) return m;
else {
if (m>n) return MCD(m-n, n);
else return MCD(m, n-m);
}
}
Calcolare il M.C.D. tra 15 e 10
Calcolare il M.C.D. tra 5 e 10
Calcolare il M.C.D. tra 5 e 5
il M.C.D. è 5.
Come è noto un numero espresso in base 10 viene convertito in un'altra base di numerazione mediante divisioni successive per la base.
Esempio. Per convertire 6 da base 10 a base 2 si divide 6 per la base 2 e si ottiene 3 con resto 0,
Si divide il quoziente 3 per la base 2 e si ottiene 1 con resto 1.
Poichè il quoziente 1 non consente di continuare le divisioni per 2, il procedimento si ferma.
la prima cifra del numero espresso in base 2 è quella dell'ultimo quoziente ottenuto (1) le cifre successive sono costituite dai resti ottenuti, presi dall'ultima verso la prima divisione. Quindi 6 espresso in base 2 è 1102 (leggere uno - uno - zero in base 2).
L'algoritmo ricorsivo si esprime nella forma seguente:
Convertire il numero N da base 10 a base B:
Se il numero N ≠ 0
allora
Converti il quoziente (N / B) nella base B
il resto tra N e B è la prossima cifra di N in base B
Esempio:
Convertire 10 in base 2:
Convertire 5 in base 2:
Convertire 2 in base 2:
Convertire 1 in base 2:
Convertire 0 in base 2:
1 è la prossima cifra di 10 in base 2
0 è la prossima cifra di 10 in base 2
1 è la prossima cifra di 10 in base 2
0 è la prossima cifra di 10 in base 2
La funzione in linguaggio C che realizza l'algoritmo è:
void cambiaBase(int N, int base) {
if (N!=0) {
cambiaBase(N/base, base);
cout << N%base << endl;
}
}
Sia dato un elenco di N elementi (numerici, stringa, ecc..) esistono N! modi in cui questi possono essere allineati.
Se l'elenco è composto da un solo elemento {a} esiste un solo modo in cui disporlo,
Se l'elenco è composto da 2 elementi {a, b} esistono 2 modi in cui disporli: ab e ba
Se l'elenco è composto da 3 elementi {a, b, c} esistono 6 modi in cui disporli: abc, acb, bac, bca, cab, cba
il procedimento in termini ricorsivi è il seguente:
Permutare un elenco di N elementi:
se l'elenco contiene almeno un elemento
allora
estrarre un elemento e posizionarlo in testa all'elenco
permutare gli N-1 elementi restanti
altrimenti la permutazione è vuota
La funzione in linguaggio C è la seguente:
void permuta (int lista[], int a, int z) {
int scambio, k;
if ((z - a) >= 1) {
for (k = z; k >= a; k--) {
scambio = lista[k];
lista[k] = lista[z];
lista[z] = scambio;
permuta (lista, a, z-1);
scambio = lista[k];
lista[k] = lista[z];
lista[z] = scambio;
}
} else /* Visualizza l'array (è una permutazione) */
}
La funzione riceve 3 parametri: il riferimento all'array contenente gli elementi da permutare (lista), gli indici degli estremi del sottoelenco da permutare (a e z).
Dopo aver dichiarato due variabili locali, Il test z-a fa procedere ad un'altra permutazione solo se l'elenco contiene almeno un elemento.
il ciclo for inizia dall'ultimo elemento e proseguendo verso il primo dell'elenco, scambia di posto l'elemento in posizione z con l'elemento di testa dell'elenco.
Richiede la permutazione degli elementi compresi tra il primo (in posizione a) e il penultimo (in posizione z-1).
Dopo la permutazione rimette i due elementi scambiati nella stessa posizione in cui si trovavano prima della permutazione.
Nel main bisogna assegnare i valori all'array lista e assegnare il valore alla variabile che rappresenta la quantità di elementi contenuti nell'array, quindi richiamare la funzione come indicato:
int main (int argc, char *argv[]) {
int i;
int lista[];
int NElem=4;
. . .
permuta (lista, 0, NElem-1);
. . .
}
Nota: bisogna assegnare il valore alla variabile NElem, il cui valore rappresenta la quantità di elementi da permutare, e i valori all'array lista.
Si prenda in considerazione il caso particolare di combinare gli elementi abcde a gruppi di 3. Si devono ottenere le seguenti combinazioni:
abc - abd - abe - acd - ace - ade
bcd - bce - bde
cde
Dall'osservazione delle combinazioni si può generalizzare il procedimento:
Combinare un elenco di N elementi a gruppi di k elementi:
se k=0 le combinazioni sono vuote, mentre se k=N l'unica combinazione possibile è costituita dagli elementi stessi.
altrimenti:
Ognuno degli elementi dell'insieme, fino a quello in posizione N-k+1, è il primo elemento di una combinazione
i restanti N-1 elementi sono una combinazione a gruppi di k-1.
a seguito da tutte le combinazioni di bcde a gruppi di 2,
b seguito da tutte le combinazioni di cde a gruppi di 1
c seguito da tutte le combinazioni di de a gruppi di 0 → abc
d seguito da tutte le combinazioni di de a gruppi di 0 → abd
e seguito da tutte le combinazioni di de a gruppi di 0 → abe
c seguito da tutte le combinazioni di de a gruppi di 1
d seguito da tutte le combinazioni di de a gruppi di 0 → acd
e seguito da tutte le combinazioni di de a gruppi di 0 → ace
d seguito da tutte le combinazioni di e a gruppi di 1
e seguito da tutte le combinazioni di (vuoto) a gruppi di 0 → ade
b seguito da tutte le combinazioni di cde a gruppi di 2,
c seguito da tutte le combinazioni di de a gruppi di 1
d seguito da tutte le combinazioni di de a gruppi di 0 → bcd
ecc.
Si scriva un programma che legga da file:
una stringa costituita da N simboli da combinare,
un intero che rappresenti la lunghezza k di una combinazione
e produca in un secondo file tutte le combinazioni possibili degli N simboli a gruppi di k.
Analizzare la codifica dell'algoritmo seguente:
| 1 | #include <string.h> |
Nel caso specifico si sta supponendo che gli elementi da combinare siano caratteri, per questo si utilizzeranno alcune funzioni per il trattamento delle stringhe.
| 2 | int Combinazione[10]; |
| 3 | int NrElem; |
| 4 | int qta; |
Linea 2: si riserva lo spazio per un array di 10 interi nel quale verranno memorizzate combinazioni di numeri.
Linea 3: Un intero contenente il numero di elementi da combinare,
Linea 4: un intero il cui valore è uguale al numero di valori memorizzati nell'array Combinazione
| 5 | void mostraComb(char Elementi[]) { |
| 6 | int i = 0; |
| 7 | for(i = 0; i < 3; i++) { |
| 8 | printf(" %c", Elementi[Combinazione[i]]); |
| 9 | } |
| 10 | printf("\n"); |
| 11 | } |
La funzione stampa il contenuto dell'array Combinazione
| 12 | void Combina(char Elementi[], int k, int Primo) { |
| 13 | if(k == 0 || k == NrElem) { |
| 14 | printf("\nOttenuta una combinazione: "); |
| 15 | mostraComb(Elementi); |
| 16 | return; |
| 17 | } |
La funzione Combina riceve come parametri: il puntatore all'array degli elementi da combinare, il numero di simboli di cui è composta una combinazione e l'indice del primo elemento da cui iniziare formare una combinazione.
Linea 13: se il numero di caratteri da combinare è 0, la lista è vuota, se invece contiene N caratteri, la combinazione è formata da tutti i simboli.
| 18 | for (int j=Primo; j<NrElem-k+1; j++) { |
| 19 | Combinazione[qta] = j; |
| 20 | qta++; |
| 21 | Combina(Elementi, k-1, j+1); |
| 22 | qta--; |
| 23 | } |
| 24 | } |
Linea 18: Ognuno dei caratteri dell'insieme dei simboli da combinare,
Linea 19: viene messo all'interno della combinazione,
Linea 20: ci si prepara ad inserire un nuovo simbolo nella combinazione.
Linea 21: si combinano i restanti elementi a iniziare da j+1 a gruppi di k-1 elementi.
Linea 22: al ritorno dalla funzione si toglie l'ultimo elemento dalla combinazione.
| 25 | int main() { |
| 26 | char Elementi[10]; |
| 27 | int Gruppi = 3; |
| 28 | int i; |
Linea 26: si riserva lo spazio per memorizzare gli elementi da combinare,
Linea 27: si assegna il valore alla lunghezza di una combinazione (modificare questa assegnazione leggendo il valore dal file.)
| 29 | qta=0; |
| 30 | printf("\nInserire gli elementi da combinare: "); |
| 31 | gets(Elementi); |
| 32 | NrElem = strlen(Elementi); |
| 33 | i=0; |
Linea 31: gli elementi da combinare vengono acquisiti da tastiera (modificare questa assegnazione leggendo il valore dal file.)
| 34 | Combina(Elementi, Gruppi, i); |
| 35 | system("PAUSE"); |
| 36 | return 0; |
| 37 | } |
Nel main viene richiamata la funzione per combinare gli elementi a gruppi di lunghezza prestabilita.
Includere la chiamata della funzione Combina in un ciclo in cui la lunghezza delle combinazioni varia da N a 1.
scrivere una funzione che cerca, ricorsivamente, il minimo in un array di interi: