[JAVA] Eccezioni e ricorsione...che cavolo stà facendo qui?

[AndreaNobili]

L'esercizio dice:
Si richiede di proggettare un metodo che esegue la ricerca binaria di un valore intero (chiave) all'interno di un array di interi ordinato in maniera non decrescente che si comporti nel seguente modo:

1) Se la chiave è contenuta nell'array, il metodo restituisce l'indice di un elemento dell'array il cui valore è uguale a quello della chiave.

2) Se la chiave non è contenuta nell'array, il metodo restituisce una descrizione della sequenza di confronti che sono stati eseguiti per decidere che la chiave non è contenuta nell'array.

Per fare sta cosa usa un'eccezione...tranne che proprio non capisco cosa stia facendo...doh

public class EccezioniComeMetodologia{
	
	public static int ricercaBinaria(int[] A, int inizio, int fine, int chiave) throws ChiaveNonTrovataException{
		
		String s;
		int posizione = -1;		// Indica la posizione dell'array dov'è stata trovata la chiave da ricercare
		
		if(fine-inizio > 0){	// Se la porzione di array in cui cercare la chiave non è ancora vuota
			try{
				if(chiave < A[(inizio+fine)/2])		// Se è verificata, la chiave và cercata nella prima metà dell'array
					posizione = ricercaBinaria(A, inizio, (inizio+fine)/2-1, chiave);
				
				else if(chiave == A[(inizio+fine)/2])
					posizione = (inizio+fine)/2;	// Chiave trovata
					
				else posizione = ricercaBinaria(A,(inizio+fine)/2+1, fine, chiave); //Se verificato la chiave deve essere cercata nella seconda metà dell'array
			}catch(ChiaveNonTrovataException e){	// Cattura l'eventuale eccezione
				// e gestiscila così:
				s = e.getMessage() + "\t cercato in posizione "+(inizio+fine)/2 + " di valore " + A[(inizio+fine)/2] + "\n";
				 throw new ChiaveNonTrovataException(s);
			}
		}
		else throw new ChiaveNonTrovataException("chiave non trovata: \n");
		
		return posizione;
	}
	
	public static void main(String[] args){
		
		int[] B = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29};
		int chiave = 4;
		int posizione = -1;
		
		try{
			posizione = ricercaBinaria(B,0,B.length-1, chiave);
			System.out.println(chiave + "trovata in posizione " + posizione);
		}catch(ChiaveNonTrovataException e){
			System.out.println(e.getMessage());
		}
	}
}

e codice dell'eccezione:

public class ChiaveNonTrovataException extends Exception{
	
	public ChiaveNonTrovataException(){
	}
	
	public ChiaveNonTrovataException(String s){
		super(s);
	}
}

Da quello che vedo esegue la normale ricerca binaria ricorsiva...tranne che non capisco dove va a sollevare l'eccezione...cioè mi pare che la sollevi nel blocco che gestisce l'eventuale eccezione (nel catch)

AHHH non capisco, mi sento stupido...help me :-(

Grazie
Andrea

[ivenuti]

la logica è questa: l'eccezione viene sollevata nel ramo else di if(fine-inizio > 0)
Essendo innescata la ricorsione, l'eccezione fa ritornare al chiamante. Il quale la intercetta e aggiunge, al messaggio originario, il messaggio con la posizione corrente. Poi risolleva l'eccezione per ritornare al chiamante che è ancora il metodo ricorsivo; così via fino alla prima invocazione...

[AndreaNobili]

mmm...vediamo se ho capito...mi ci impicco sempre con la ricorsione...poi mettendoci in mezzo anche le eccezioni peggio mi sento....

Io ho l'array iniziale:

B = {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29}
e la chiave da ricercare pari a 4.

1) Passo l'array alla prima invocazione del metodo RicercaBinaria...lo confronta con l'elemento centrale ( A[(inizio+fine)/2]) che è l'elemento di indice 7, che contiene il valore 15

--> 4 < 15 --> Siamo nel primo caso e viene rinvocato ricorsivamente il metodo RicercaBinaria sulla prima metà dell'array perchè se la chiave è presente nell'array deve essere per forza nella prima metà visto che è ordinato in maniera non decrescente.

2) Alla seconda invocazione ricorsiva del metodo arriva la prima metà dell'array (meno 1 perchè era l'elemento che aveva controllato all'invocazione prima: B = {1,3,5,7,9,11,13}

Come prima prende l'elemento di mezzo e lo confronta con la chiave da ricercare, quindi in questo caso l'elemento in posizione 3 che contiene il valore 7: 4 < 7 --> se c'è,la chiave è nella prima metà dell'array...rinvoco ricorsivamente sulla prima metà di tale array

3) Alla terza invocazione ricorsiva del metodo arriva la prima metà dell'array: B = {1,3,5} e confronta con l'elemento di mezzo: (4>3) ed invoca sulla seconda metà dell'array:

4) All quarta invocazione del metodo ricorsivo arriva B ={5} e si accorge che l'array è finito e che l'elemento cercato non è presente nell'arrya di partenza perchè if(fine-inizio > 0) FALLISCE e quindi viene sollevata una ChiaveNonTrovataException....

Ora per sua natura la 4 invocazione della routine ricorsiva "torna indietro" restituendo alla terza invocazione non il risultato ma l'eccezione, la terza invocazione gestisce tale eccezione in questo mod:

1) Stampa il messaggio: "cercato in posizione 1 di valore 3"
2) Solleva una nuova ChiaveNonTrovataException(s) che viene restituita al chiamante (la seconda invocazione del metodo ricorsivo).

La seconda invocazione del metodo ricorsivo riceve l'eccezione ritornata e fà:

1) Stampa il messaggio: "cercato in posizione 3 di valore 7"
2) Solleva una nuova ChiaveNonTrovataException(s) che viene restituita al chiamante (la prima invocazione del metodo ricorsivo).

La prima invocazione del metodo ricorsivo fà altrettanto e così via...

Per favore...mi sapresti dire se è corretto questo ragionamento?
Ma sono scemo io a trovarlo un po' cervellotico o è oggetivamente un po' complesso?

Grazie
Andrea