[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 :mano:

[franksisca]

UNICAL :confused: :confused: :confused:


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

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 :boh:

[jappilas]

non va perchè messa in quel modo mi pare NON sia ricorsiva ...
la ricorsione si basa sul principio di induzione (http://www.mokabyte.it/2003/03/ricorsione.htm)
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... :rolleyes:
ti basta fare un check iniziale (if s.length()>1) return s else ...

[^TiGeRShArK^]

odio la ricorsione! :muro:

[luxorl]

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 :p 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. :mbe:

[pisto]

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. :mbe:

mettiamocelo in testa che i copmputer sono stupidi! :D :D
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]

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. :mbe:


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... :sofico: