[Java] Devo imparare a creare metodi ricorsivi... da dove comincio?

[luxorl]

Ciao,
premetto che sono a buon livello di programmazione orientata agli oggetti in java. Però quando si tratta di svolgere qualche esercizio dove bisogna implementare metodi ricorsivi vado nel pallone...

Sapete consigliarmi una guida on-line che mi possa aiutare?
O come mi consigliate di procedere per imparare bene la programmazione ricorsiva?

come sempre: Grazie

[franksisca]

UNICAL


La ricorsione???
Guarda, io ho trovato di peggio, il BACKTRACKING!!!

prova sui libri della mokabyte, thinking in java e prova qualche manuale, tipo tecniche avanzate in java, altrimenti non saprei davvero dove reindirizzarti.CIAO

[luxorl]

Ho qui con me l'Horstmann (Java 2 i Fondamenti) ma MI SEMBRA che non ci sia scritto niente a riguardo..

[luxorl]

Per esempio dovrei scrivere un metodo che accetta una stringa e restituisce un'altra stringa che è il contrario di quella accettata. Questo metodo deve essere ricorsivo.

Non è che potete darmi uno spunto su come risolvere questo problema?

[luxorl]

Io avevo pensato a qualcosa del genere:

public class StringaRicorsiva{

	public static String reverse(String s){
		for(int i=0; i<s.length(); i++){
		String s2=s.charAt(s.length()-1)+s.substring(0, s.length()-2);
		reverse(s);
		}
		return s;
	}

	public static void main(String args[]){
		String s="speriamo";
		String c=reverse(s);
		System.out.println(c);
	}
}

ma non va

[jappilas]

non va perchè messa in quel modo mi pare NON sia ricorsiva ...
la ricorsione si basa sul principio di induzione
applicato al caso della string reverse deriverebbe qualcosa del genere (che poi devi far sì che la funzione, implementi):

1)reverse (a) = a
2)reverse (a + str) = reverse (str) + a

1) è la funzione minima per la stringa di un solo carattere
con 2) reverse() invoca ripetutamente sè stessa finchè non si arriva al caso del singolo carattere: in questo è ricorsiva

nel tuo caso mi pare che il ciclo for nella funzione vanifichi di fatto la ricorsione, inoltre chiami la funzione con lo stesso parametro (s) che hai in ingresso...
ti basta fare un check iniziale (if s.length()>1) return s else ...

[^TiGeRShArK^]

odio la ricorsione!

[luxorl]

Originariamente inviato da jappilas

ti basta fare un check iniziale (if s.length()>1) return s else ...

(if s.length()< 1) return s else...

Comunque dopo una notte insonne ce l'ho fatta!!

public class StringaRicorsiva{

	public static String reverse(String s){
		if(s.length()<1) return s;
		else{
		s=s.charAt(s.length()-1)+reverse(s.substring(0, s.length()-1));
		return s;
		}
	}


	public static void main(String args[]){
		String s="speriamo";
		String c=reverse(s);
		System.out.println(c);
	}
}

Una sola cosa:

se tolgo l'ultimo return s, il compilatore si arrabbia dicendo che manca il ritorno.. però logicamente prima o poi l'if sarà true quindi il ritorno ci sarà.. ma bisogna mettere comunque quel return s finale per accontentare il compilatore?

Senza non mi compila.

Originariamente inviato da luxorl

se tolgo l'ultimo return s, il compilatore si arrabbia dicendo che manca il ritorno.. però logicamente prima o poi l'if sarà true quindi il ritorno ci sarà.. ma bisogna mettere comunque quel return s finale per accontentare il compilatore?

Senza non mi compila.

mettiamocelo in testa che i copmputer sono stupidi!
però comunque è logico: metti che dopo il return ci sia ancora qualcosa da fare nel metodo: la jvm cosa fa, continua l'esecuzione del codice che ha richiamato il metodo (come dovrebbe fare, visto che ha ricevuto i dati in ritorno), o ciò che manca del metodo? visto che i due non sono due trhead, è alcuanto un problema...

[51078]

Originariamente inviato da luxorl

Una sola cosa:

se tolgo l'ultimo return s, il compilatore si arrabbia dicendo che manca il ritorno.. però logicamente prima o poi l'if sarà true quindi il ritorno ci sarà.. ma bisogna mettere comunque quel return s finale per accontentare il compilatore?

Senza non mi compila.

Succede perchè il return non può essere messo solo in una porzione di codice soggetta a condizioni, in quanto potrebbe non essere mai soddisfatta e quindi la funzione non ritornerebbe mai, questo a prescindere dal fatto che la condizione sia palesemente soddisfacibile, il compilatore non valuta questi fattori...




P.S. : Per la ricorsione quoto jappilas, devi sempre tenere presente che serve un caso base che determina la fine della ricorsione e il passo ricorsivo va fatto sempre in forma generale... Se vuoi far pratica usa un po PROLOG, poi diventi un mago della ricorsione...