Programmazione a Oggetti e

JAVA

Prof. B.Buttarazzi

A.A. 2012/2013

16/01/2013 2

Sommario

• La ricorsione

• Metodi ricorsivi

• Esercizi proposti

3

In Java ogni metodo può chiamare anche se stesso, secondo

una tecnica detta ricorsione.

Ovviamente tali metodi devono sempre contenere un’istruzione

di controllo che ha il compito di interrompere la successione

delle chiamate, se si verificano certe condizioni.

La ricorsione

4.11.2004 4

Il calcolo del fattoriale

La funzione fattoriale, molto usata nel calcolo

combinatorio, è così definita

dove n è un numero intero non negativo

0 se

0 se

)!1(

1!

n

n

nnn

5

Confronto fra definizione iterativa e ricorsiva

Funzione non ricorsiva

n!= 1*2*3*...*(n-1)*n

fatt(n)= 1*2*3*...*(n-1)*n;

Funzione ricorsiva

0!=1

n!= n*(n-1)!;

fatt(n)=n*fatt(n-1)

Il calcolo del fattoriale

• Vediamo di chiarirne il significato

0! = 1

1! = 1(1-1)! = 1·0! = 1·1 = 1

2! = 2(2-1)! = 2·1! = 2·1 = 2

3! = 3(3-1)! = 3·2! = 3·2·1 = 6

4! = 4(4-1)! = 4·3! = 4·3·2·1 = 24

5! = 5(5-1)! = 5·4! = 5·4·3·2·1 = 120

• Quindi, per ogni n intero positivo, il fattoriale di n è il prodotto dei primi n numeri interi positivi

7

Il calcolo del fattoriale

• Per implementare la funzione per il calcolo del fattoriale

con un metodo statico iterativo siamo costretti a fare

un’analisi della definizione per scrivere l’algoritmo

8

Il calcolo del fattoriale

• Per implementare la funzione per il calcolo del fattoriale

con un metodo statico iterativo siamo costretti a fare

un’analisi della definizione per scrivere l’algoritmo:

public static float fattoriale (int n) {

float F=1;

int i=1;

do {

F=F*i;

i=i+1;

}

while (i<=n);

return F;

Il calcolo del fattoriale

• Implementando direttamente la definizione ricorsiva, è naturale scrivere:

public static float fattoriale (int n)

{

float f;

if (n == 0) f = 1;

else f = n * fattoriale(n - 1);

return f;

}

Il calcolo del fattoriale

• Implementando direttamente la definizione ricorsiva, è naturale scrivere:

public static float fattoriale (int n)

{

float f;

if (n == 0) f = 1;

else f = n * fattoriale(n - 1);

return f;

} Questa soluzione si basa sulla invocazione di un metodo mentre si esegue il metodo stesso!

Questa possibilità è permessa in tutti i linguaggi di programmazione che ammettono la ricorsione

Il calcolo del fattoriale

public static float fattoriale (int n)

{

float f;

if (n == 0) f = 1;

else f = n * fattoriale(n - 1);

return f;

} Questa soluzione si basa sul fatto invocare un metodo mentre si esegue il metodo stesso!

Questa possibilità è lecito in tutti i linguaggi di programmazione che ammettono la ricorsione

La funzione ricorsiva fattoriale non necessita di iterazioni, ma include internamente il

calcolo del risultato, infatti restituisce 1 se il parametro ricevuto uguale a 0 mentre in

caso contrario il valore restituito è il prodotto di n per il fattoriale (n-1), pertanto

fattoriale calcola il valore da restituire chiamando se stessa e "passandosi" come

parametro il parametro appena ricevuto, diminuito di uno.

4.11.2004 12

La ricorsione Per capire come utilizzare correttamente la ricorsione, vediamo innanzitutto come funziona.

Quando un metodo ricorsivo invoca se stesso, la macchina virtuale Java esegue le stesse azioni che vengono eseguite quando viene invocato un metodo qualsiasi

– sospende l’esecuzione del metodo invocante (le variabili locali rimangono congelate)

– esegue il metodo invocato fino alla sua terminazione (con nuove variabili locali e passando i parametri per valore)

– riprende l’esecuzione del metodo invocante dal punto in cui era stata sospesa (recuperando le variabili locali)

La ricorsione • Vediamo la sequenza delle istruzioni per calcolare 3!

si invoca f(3)

f(3) lascia in sospeso il calcolo 3* f(2) e invoca f(2)

f(2) lascia in sospeso il calcolo 2* f(1) invoca f(1)

f(1) lascia in sospeso il calcolo 1* f(0) e invoca f(0)

f(0) restituisce 1 a f(1)

f(1) calcola1*1 e restituisce 1 a f(2)

f(2) calcola 2*1 e restituisce 2 a f(3)

f(3) calcola 3*2 e restituisce 6 al chiamante

• Si crea quindi una pila ( stack) di metodi “in attesa”, ciascuno con le sue variabili locali, che si allunga e che poi si accorcia fino ad esaurirsi

4.11.2004 14

La ricorsione • Invocare un metodo mentre si esegue lo stesso metodo è un

paradigma di programmazione che si chiama

ricorsione

e un metodo che ne faccia uso si chiama

metodo ricorsivo

• La ricorsione è uno strumento molto potente per realizzare

alcuni algoritmi (ma è anche fonte di errori di difficile

diagnosi)

• Esistono infatti due regole ben definite (passo base e passo

ricorsivo) che vanno utilizzate per scrivere metodi ricorsivi

che funzionino

4.11.2004 15

Prima regola La ricorsione: passo base

– il metodo ricorsivo deve fornire la soluzione del

problema in almeno un caso particolare, senza

ricorrere ad una chiamata ricorsiva

– tale caso si chiama caso base della ricorsione

– nel nostro esempio, il caso base era

– a volte ci sono più casi base, non è necessario che il

caso base sia unico

if (n == 0) return 1;

4.11.2004 16

Seconda regola La ricorsione: passo ricorsivo

– il metodo ricorsivo deve effettuare la chiamata

ricorsiva dopo aver semplificato il problema

– nel nostro esempio, per il calcolo del fattoriale di n si

invoca la funzione ricorsivamente per conoscere il

fattoriale di n-1, cioè per risolvere un problema più

semplice

– il concetto di “problema più semplice” varia di volta in

volta: in generale, bisogna avvicinarsi ad un caso base

f = n * fattoriale(n - 1);

4.11.2004 17

Ricorsione infinita • Si noti quindi che non tutti i metodi ricorsivi

realizzano algoritmi!

– se manca il caso base, il metodo ricorsivo continua ad invocare se stesso all’infinito

– se il problema non viene semplificato ad ogni invocazione ricorsiva, il metodo ricorsivo continua ad invocare se stesso all’infinito

• Dato che la lista dei metodi “in attesa” si allunga indefinitamente, l’ambiente runtime esaurisce la memoria disponibile per tenere traccia di questa lista, e il programma termina con un errore.

4.11.2004 18

Le regole appena viste

• implicano che ad ogni invocazione il problema diventi più

semplice avvicinandosi sempre più al caso base che non

richiede ricorsione

• ovvero che per quanto complesso possa essere il problema

la soluzione sia calcolata in un numero finito di passi

Ricorsione infinita

Esercizio

Vediamo la codifica di tale funzione in modo iterativo

Vediamo come si semplifica la soluzione ricorsiva

/* algoritmo iterativo */

public static long iterFibonacci(int n){

if(n<=1) return n;

long x=0; long y=1; long tmp;

for(int i=2; i<=n; i++){

tmp = x; x = y; y = tmp+x;

// dopo l'i-esima iterazione: x=F(i-1), y=F(i)

}

return y;

}}

public static float fibo (int n) {

float fib;

if (n == 0) {

fib = 0;

} else if (n == 1) {

fib = 1;

} else {

fib = fibo(n-1)+ fibo(n-2);

}

return fib;

}

public static float fib (int n) {

{ if (n < 2) { return n; }

else { return fib(n-1)+fib(n-2); } } }

…….osservazioni

La semplicità del codice ha un costo che studieremo quando parleremo di complessità per il momento basta osservare che ad ogni chiamata vengono genereate 2 variabili…quindi si occupa più memoria.

Esercizi

• Scrivere un metodo statico ricorsivo per il

calcolo della funzione esponenziale definita

come segue:

16/01/2013 24

Esercizi

• Scrivere un metodo statico ricorsivo per il

calcolo della funzione esponenziale definita

come segue:

16/01/2013 25

Esercizi

• Scrivere un metodo statico che, dati un

array di interi a ed un intero n, restituisce il

numero delle occorrenze di n in a

16/01/2013 26

Esercizi

• Scrivere un metodo statico che, dati un

array di interi a ed un intero n, restituisce la

posizione della prima occorrenza di n in a, e

-1 se n non compare in a.

16/01/2013 27

Esercizi

• Scrivere un metodo statico che, dati un

array di interi a ed un intero n, restituisce

true se n compare in a, false altrimenti.

16/01/2013 28

Esercizi

• Scrivere un metodo statico che, dati un

array bidimensionale di interi a ed un intero

n, restituisce true se n compare in a, false

altrimenti.

16/01/2013 29

Esercizi

• Scrivere un metodo statico che dato un

array di interi restituisca true se tutti i suoi

elementi sono identici, e false altrimenti.

16/01/2013 30

Esercizi

• Scrivere un metodo che, dati un array

bidimensionale di interi a e due interi k ed

n, restituisce true se in ogni riga a[i] di a

esistono almeno k elementi maggiori di n,

altrimenti il metodo restituisce false.

16/01/2013 31

Cosa abbiamo imparato?

• Come funziona la ricorsione: il processo

secondo il quale un metodo può anche

richiamare se stesso;

• Che cos’è un metodo ricorsivo: ossia un

metodo che fa uso della ricorsione;

• Che cos’è la ricorsione infinita.

16/01/2013 32

Questionario 1)Quali dei seguenti programmi è errato per calcolare il fattoriale di un

numero in Java?

□ class Fattoriale {

static float fatt(int x) {

int i;

float f=1;

do{

f=f*i;

i= i+1; }

while(i<=x);

return f;

};

□ class Fattoriale {

static int fatt(int x) {

int i;

int f=1;

for(i=1; i<=x; i=i+1) {

f=f*i; }

return f;

}; 16/01/2013 33

16/01/2013 34

□ public class Fattoriale {

public static void main(String[] args) {

int n, i;

long fatt;

if (args.length > 0) {

n = Integer.parseInt(args[0]);}

else {

n = MyUtility.readInt("Inserisci N: ");}

fatt = 1;

for (i = 1; i <= n; i++) {

fatt *= i;}

System.out.println(n+"! = "+fatt);}

};

□ class Fattoriale {

static float fatt(float x) {

int i;

int f=1;

for(i=1; i<=x; i=i+1) {

f=f*i;}

return f;

};

16/01/2013 35

2)A cosa serve la ricorsione?

□ Ad invocare un metodo di un’altra classe;

□ Ad eseguire un metodo uno dopo l’altro;

□ Ad invocare un metodo dopo che il metodo stesso è stato eseguito;

□ Ad invocare un metodo mentre si esegue lo stesso metodo.

3)Quali delle seguenti non è un’azione che esegue la JVM quando viene invocato un

metodo ricorsivo?

□ Sospendere l’esecuzione del metodo invocante;

□ Eseguire il metodo invocato fino alla sua terminazione recuperando le variabili locali;

□ Riprendere l’esecuzione del metodo chiamante dal punto in cui era stato sospeso;

□ Eseguire il metodo invocato fino alla sua terminazione.

4) Nei programmi scritti nella domanda 1 è presente almeno un passo ricorsivo?

□ Si in tutti i 4 programmi;

□ No in nessuno dei 4 programmi;

□ Solo nel secondo programma;

□ Solo nel terzo programma.

5) Nei programmi scritti nella domanda 1 è presente almeno un caso base?

□ Si in tutti i 4 programmi;

□ No in nessuno dei 4 programmi;

□ Solo nel secondo programma;

□ Solo nel terzo programma.

16/01/2013 36

6)Quali sono le regole che bisogna seguire per scrivere un metodo ricorsivo?

□ Il metodo deve fornire la soluzione del problema in almeno un caso particolare, e

deve effettuare la chiamata ricorsiva dopo aver semplificato il problema;

□ Il metodo deve fornire la soluzione del problema in almeno un caso particolare,

ricorrendo ad una chiamata ricorsiva e deve effettuare di nuovo la chiamata dopo aver

semplificato il problema;

□ Il metodo deve fornire la soluzione del problema in più di un caso particolare, e deve

effettuare la chiamata ricorsiva dopo aver semplificato il problema;

□ Il metodo deve semplificare il problema e deve poi effettuare la chiamata ricorsiva .

7)Quale delle seguenti affermazioni sulla ricorsione è esatta ?

□ Ad ogni invocazione del metodo il problema diventa sempre più complesso;

□ Anche la soluzione del caso base richiede l’uso della ricorsione;

□ Bisogna effettuare la chiamata ricorsiva dopo aver semplificato il problema;

□ Il passo ricorsivo non può essere messo all’interno di un’espressione .

8)In quale caso non si ha ricorsione infinita?

□ Se il problema viene semplificato ad ogni invocazione ricorsiva;

□ Se manca il caso base;

□ Se il problema non viene semplificato ad ogni invocazione ricorsiva;

□ Se il problema viene semplificato solo alla prima invocazione ricorsiva.

16/01/2013 37

9)Quale delle seguenti è un esempio di funzione ricorsiva?

□ n!=1*2*3*…*(n-1)*n;

□ fatt(n)=n*fatt(n-1);

□ fatt(n)= 1*2*3*...*(n-1)*n;

□ 3!=6.

10)Quali dei seguenti programmi non è corretto per calcolare la sequenza di

Fibonacci in maniera ricorsiva?

□ class Fibonacci {

public static long fibo(long n) {

if(n<=1) return n;

else return fibo(n-1)+ fibo(n-2); }

};

□ class Fibonacci {

public static long fibo(long n) {

if(n<=1) return n;

else return fibo(n-1)+ fibo(n-2);}

public static void main(String args[]) {

long n = Integer.parseInt(args[0]);

System.out.println("fib(" + n + ")=" + fibo(n));}

};

16/01/2013 38

□ class Fibonacci {

public static long fibo(long n) {

long fibN_1 = 0, fibN_2 = 1, fibN=1;

if(n<=1) return n;

else {

for(int i=2; i<=n; i++) { fibN=fibN_1+fibN_2; fibN_1=fibN_2; fibN_2=fibN; }

return fibN; }

}

};

□ class Fibonacci {

public static long fibo(int n) {

if(n<=1) return n;

else return fibo(n-1)+ fibo(n-2);}

}.

11)Nei programmi della domanda 10 è presente almeno un caso base?

□ Si in tutti i 4 programmi;

□ No in nessuno dei 4 programmi;

□ Si nel secondo e nel terzo programma;

□ Si nel primo e nell’ultimo;

□ Si in tutti tranne nel terzo;

□ Si in tutti ad eccezione del primo.

16/01/2013 39

12)Nel terzo programma della domanda 10 qual è il caso base?

□ return n;

□ return fibN;

□ if(n<=1) return n;

□ for(int i=2; i<=n; i++) { fibN=fibN_1+fibN_2; fibN_1=fibN_2; fibN_2=fibN; }

return fibN.

13) Nei programmi della domanda 10 è presente un passo ricorsivo?

□ Si in tutti i 4 programmi;

□ No in nessuno dei 4 programmi;

□ Si nel secondo e nel terzo programma;

□ Si nel primo e nell’ultimo;

□ Si in tutti tranne nel terzo;

□ Si in tutti ad eccezione del primo.

14) Qual è il passo ricorsivo presente nel secondo programma della domanda 10?

□ return fibo(n-1)+ fibo(n-2);

□ fibo(n-1)+ fibo(n-2);

□ long n = Integer.parseInt(args[0]);

System.out.println("fib(" + n + ")=" + fibo(n));;

□ if(n<=1) return n;

else return fibo(n-1)+ fibo(n-2);.

16/01/2013 40

15) Quali delle seguenti opzioni è corretta per dichiarare un metodo media() che

dispone di un tipo restituito double e due parametri interi x e y?

□ double media(x, y) {…;

□ double media( int x, int y) {…;

□ double Media( int x, int y) {…;

□ public double Media(x, y) {…;

16) Per lo studio di quali funzioni può essere utilizzato il metodo della ricorsione?

□ Per il calcolo del fattoriale;

□ Per il calcolo del fattoriale e per la sequenza di Fibonacci;

□ Per il calcolo delle funzioni goniometriche;

□ Per il calcolo del fattoriale, per la sequenza di Fibonacci e per le funzioni

goniometriche.

Esercizio

Scrivere una programma Java che realizza il gioco “indovina che numero

ho pensato”, descritto come segue:

•inizialmente, il programma genera un numero casuale intero

compreso tra 1 e 100 e lo sceglie, e poi chiede all’utente di indovinare

il numero scelto

•dopo ciascun tentativo di risposta dell’utente, l’applicazione deve

segnalare se la risposta data è giusta, oppure il numero è maggiore

oppure il numero è minore rispetto al numero scelto

•il programma deve continuare a chiedere numeri all’utente fino a che

questi non abbia dato la risposta corretta, oppure abbia scelto di

rinunciare ad indovinare (digitando il numero 0)

•se l’utente indovina il numero scelto, il programma deve congratularsi

con l’utente, visualizzando anche il numero di tentativi fatti dall’utente

16/01/2013 41

16/01/2013 42

Ad esempio, se il numero scelto dal programma fosse 21, l’interazione tra

applicazione e utente potrebbe essere la seguente

–Ho pensato un numero intero compreso tra 1 e 100.

–Indovina che numero ho pensato: 40–40 è troppo alto.

–Indovina che numero ho pensato: 30–30 è troppo alto.

–Indovina che numero ho pensato: 20–20 è troppo basso.

–Indovina che numero ho pensato: 22–22 è troppo alto.

–Indovina che numero ho pensato: 21

–Bravo! Hai indovinato facendo 5 tentativi!