Gocce di Java: ricorsione in programmazione per l'Università

Metodi e ricorsione

Ricorsione

Strumento potente per manipolazione di strutture matematiche Consente semplice formulazione di algoritmi Consente semplice dimostrazione di correttezza di algoritmi

Metodi ricorsivi

Direttamente ricorsivi Invocano sè stessi Indirettamente ricorsivi Invoca un altro metodo che invoca (direttamente o indirettamente) primo metodo34

Metodi e ricorsione

Ricorsione

Metodo direttamente ricorsivo per cercare numero intero in array ordinato

boolean esiste (int[] a, int l, int r, int k) { if (l > r ) { return false ; } else { int m = (l +r )/2; if (a [m] == k) { return true ; } else { if (k

Metodi e ricorsione

Ricorsione

Metodi indirettamente ricorsivi

void stampaNumeroDispari ( int n ) { System. out. println ( "Numero dispari: "+n ) ; if (n>1) { stampaNumeroPari ( n-1 ) ; } } void stampaNumeroPari ( int n ) { System . out . println ( "Numero pari: "+n ) ; stampaNumeroDispari ( n-1 ); } void stampa ( int n ) { if (n %2 == 0 ) { stampaNumeroPari ( n ) ; } else { stampaNumeroDispari ( n ) ; } }36

Metodi e ricorsione

Ricorsione

Metodi ricorsivi e numerologia

Numero del destino

Somma cifre data di nascita ripetuta sino a quando si ottiene una sola cifra Esempio: 21 Giugno 1961 21061961 2+1+0+6+1+9+6+1=26 2+6=8 Numero del destino: 8 2 ?37

Metodi e ricorsione

Ricorsione

int sommaCifre ( int numero ) { int risultato = 0; while (numero >0) { risultato += numero%10; numero = numero /10; } return risultato; } int destino ( int numero ) { int temp = sommaCifre ( numero ) ; if (numero >9) return destino ( temp ) ; else return temp ; } void main () { int n = Input . getInt ( "Data ( GGMMAAAA ) " ) ; System. out. println( "Destino: "+destino ( n ) ) ; }38

Metodi e ricorsione

Ricorsione

Caso base

In una procedura ricorsiva oltre all'invocazione della procedura stessa (ricorsione) è fondamentale il "caso base", in cui è definita un'istruzione che termina la procedura (e quindi anche la ricorsione) senza caso base una procedura ricorsiva è destinata a non terminare mai.39

Metodi e ricorsione

Ricorsione

Profondità della ricorsione

Il numero di chiamate necessarie per raggiungere la condizione di terminazione. Ogni chiamata ricorsiva richiede la memorizzazione delle variabili locali, parametri e stato attuale della computazione Quindi una ricorsione profonda richiede molta memoria In alcuni casi e quando possibile si dovrebbero preferire implementazioni iterative. In alcuni casi, è facile trasformare metodo ricorsivo in metodo non ricorsivo Schema A = if(E) {S; A} Schema A = S; if (E) { A} =40

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

In alcuni casi, è facile trasformare metodo ricorsivo in metodo non ricorsivo Schema A = if(E) {S; A} Diventa A = while(E) {S} Schema A = S; if (E) { A} Diventa A = do{S}while(E);41

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Ricorsione e fattoriale di un numero

Metodo ricorsivo

int fattorialeRicorsivo ( int n ) { if (n>1) { return n*fattorialeRicorsivo ( n-1 ); } else { return 1; } } Metodo non ricorsivo Già visto: fa uso di for42

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Numeri di Fibonacci

Divertissement matematico Crescita popolazione conigli Una coppia all'inizio Ogni coppia diviene fertile dopo 1 mese Ogni coppia fertile riproduce una nuova coppia ogni mese Quante coppie di conigli dopo n mesi? Mese 0 1 Mese 1 1 Mese 2 2 Mese 3 3 Mese 4 5 Mese 5 8 Fn = Fn-1 + Fn-2 Fn-1: coppie già esistenti Fn-2: coppie nuove43

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Metodo ricorsivo

long fiboRic ( int n ) { if (n<2) { return 1; } else { return fiboRic( n-1 )+fiboRic( n-2 ) ; } } Albero delle chiamate ricorsive 5 4 3 3 2 2 1 2 1 1 0 1 0 1 044

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Metodo iterativo

long fibonacci ( int n ) { int i = 0; long x = 1, y = 0; while (i

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Altri esempi

Vedere sul libro Le torri di Hanoi Curve di Hilbert Generazione di sequenze binarie e permutazioni46

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Ricorsione e divide-et-impera

Tecnica di progettazione di algoritmi, basata sulla ricorsione Si basa sulla scomposizione in sotto-problemi più semplici In questo caso i problemi più semplici sono lo stesso problema ma con input "più piccolo"

1. Decomposizione in sotto-problemi
2. Soluzione ricorsiva dei sotto-problemi
3. Ricombinazione delle soluzione dei sotto-problemi47

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Ricorsione e divide-et-impera

Ordinamento per fusione

1. Decomposizione in sotto-problemi: se almeno due elementi, divide in due sotto-array uguali
2. Soluzione ricorsiva: ordina ricorsivamente due sotto-array
3. Ricombinazione delle soluzioni: fonde due sotto-array ordinati in un array ordinato

Implementazione

void ordina ( int [] a, int sinistra, int destra) { if ( sinistra < destra) { int centro = (sinistra + destra) / 2; ordina (a, sinistra, centro); ordina (a, centro + 1, destra) ; fondi (a, sinistra, centro, destra); } }48

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

void fondi (int [] a, int s, int c, int d) { int [] b = new int [d-s+1] ; int i = s, j = c + 1, k = 0; while ((i <= c) && (j <= d) ) { if (a[i]

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Fusione con array di appoggio

sinistra centro destra - > a 6 7 9 11 12 8 10 15 13 14 b a 6 7 9 11 12 8 10 15 13 14 b 8 a 6 7 9 11 12 8 10 15 13 14 b 8 10 a 6 7 9 11 12 8 10 15 13 14 b 8 10 13 a 6 7 9 11 12 8 10 15 13 14 b 8 10 13 14 a 6 7 9 11 12 8 10 15 13 14 b 8 10 13 14 15 a 6 7 9 11 12 8 10 13 14 15 b 8 10 13 14 1550

Metodi e ricorsione

Ricorsione - Ricorsione e iterazione

Albero delle chiamate ricorsive

7,11,9,6,12,15,8,10,14,13 7,11,9,6,12 15,8,10,14,13 7,11,9 6,12 15,8,10 14,13 7,11 9 6 12 15,8 10 14 13 7 11 15 8