[JAVA] - metodi ricorsivi

[tigerjack89]

Ciao ragazzi!! Come da titolo sto cercando di capire l'uso di questi stramaledetti metodi ricorsivi!
Non riesco davvero a capirli per bene; qualcuno di voi potrebbe segnalarmi gentilmente qualche link dove studiarli per bene e che vada oltre gli esempi base??

Detto questo...ho parecchi esercizi da risolvere; eccone uno:
Premesse: ho una classe Sentence il cui costruttore è public Sentence(String text); nell'esercizio precedente ho realizzato un metodo boolean find(String t) che verifica se la stringa t è contenuta nella frase.

Usate la ricorsione per realizzare un metodo int indexOf(String t) che restituisce la posizione iniziale della prima sottostringa del testo che sia uguale alla stringa t. Restituite –1 se t non è una sottostringa di s. Ad esempio:

Sentence s = new Sentence(“Mississippi!”);
int n = s.indexOf(“sip”); // restituisce 6

Suggerimento: questo è un po’ più difficile del problema precedente, perché dovete tenere traccia di quanto sia lontana dall’inizio della frase la corrispondenza che state cercando; inserite tale valore come parametro di un metodo ausiliario.

Voi come realizzereste un metodo del genere?? Soprattutto, seguendo quale ragionamento???
So che questo problema può risolversi benissimo in altri modi, ma vorrei capire che ragionamento fare per arrivare a realizzare un metodo ricorsivo.

Grazie mille in anticipo a tutti coloro che avranno voglia di perdere tempo con me

[francesco.muia]

Ciao,
Per quanto riguarda i metodi ricorsivi non sò indicarti nessun sito in cui se ne parla. Per quanto rigurda la soluzione al tuo esercizio potrebbe essere questa:

package it.underline.contribuzioni.entity.dao;

public class StringUtils
{
	private String myString;

	public StringUtils(String string)
	{
		myString = string;
	}

	public int indexOf(String aString)
	{
		if (aString.length() <= this.myString.length())
		{
			return this.indexOf(0, aString.length(),aString);
		}
		else
		{
			return -1;
		}
	}

	private int indexOf(int startIndex,int toIndex, String aString)
	{
		if(toIndex > this.myString.length())
		{
			return -1;
		}
		String subString = myString.substring(startIndex,toIndex);
		if (aString.equals(subString))
		{
			return startIndex;
		}
		else
		{
			return indexOf(++startIndex,++toIndex,aString);
		}
	}
	public static void main(String[] args)
	{
		System.out.println(new StringUtils("Mississippi!").indexOf("pippo"));
	}
}

[tigerjack89]

Originariamente inviato da francesco.muia
Ciao,

Grazie mille, veloce ed efficace come sempre
Ora mi studio per bene la soluzione e nel caso ho dei dubbi posto qui.

Puoi spiegarmi solo una cosa? Come fai a sviluppare un metodo ricorsivo del genere? Cioè, da che presupposti parti, che ragionamenti fai? Usando un espressione pokeristica: qual è il tuo thinking process? Perchè in questi casi io non so proprio da dove iniziare!!

[francesco.muia]

Parto dal concetto di ricorsione matimatica link e la applico alla costruzione del metodo. Detta in maniera veramente orrenda si può dire che un metodo è ricorsivo se chiamo più volte lui stesso.

[tigerjack89]

Originariamente inviato da francesco.muia
Parto dal concetto di ricorsione matimatica link e la applico alla costruzione del metodo. Detta in maniera veramente orrenda si può dire che un metodo è ricorsivo se chiamo più volte lui stesso.

yez il concetto l'ho capito. Il fatto è che mi riesce proprio difficile pensare in maniera ricorsiva

[tigerjack89]

return indexOf(++startIndex,++toIndex,aString);

Una domanda su questo punto: perchè incrementi anche toIndex? Non si dovrebbe incrementare solo startIndex???
Lo so che queste domande possono sembrare scontate ma abbi pietà

[francesco.muia]

Originariamente inviato da tigerjack89

return indexOf(++startIndex,++toIndex,aString);

Una domanda su questo punto: perchè incrementi anche toIndex? Non si dovrebbe incrementare solo startIndex???
Lo so che queste domande possono sembrare scontate ma abbi pietà

Gli indici non si incrementano mai da soli, entrabi servono a settare la porzione di stringa in cui cercare

[tigerjack89]

Originariamente inviato da francesco.muia
Gli indici non si incrementano mai da soli, entrabi servono a settare la porzione di stringa in cui cercare

Perfetto, rivedendo il metodo capisco perfettamente il perchè

Grazie mille ancora

[VincenzoTheBest]

Originariamente inviato da tigerjack89
yez il concetto l'ho capito. Il fatto è che mi riesce proprio difficile pensare in maniera ricorsiva

Allora definisci prima la soluzione iterativa, e quindi ottieni quella ricorsiva.

Originariamente inviato da tigerjack89
Una domanda su questo punto: perchè incrementi anche toIndex? Non si dovrebbe incrementare solo startIndex???

In effetti puoi utilizzare anche un solo indice:

public int indexOf(String str, String sub){
       if ( sub.length() > str.length() )
            return -1;
       return indexOf(str, sub, 0);
}

private int indexOf(String str, String sub, int i){
        if( i+sub.length() > str.length() ) 
            return -1;

        if( sub.equals( str.substring(i, i+sub.length()) ) )
            return i;
        return indexOf(str, sub, i+1);
}

[francesco.muia]

Originariamente inviato da VincenzoTheBest
Allora definisci prima la soluzione iterativa, e quindi ottieni quella ricorsiva.


In effetti puoi utilizzare anche un solo indice:

public int indexOf(String str, String sub){
       if ( sub.length() > str.length() )
            return -1;
       return indexOf(str, sub, 0);
}

private int indexOf(String str, String sub, int i){
        if( i+sub.length() > str.length() ) 
            return -1;

        if( sub.equals( str.substring(i, i+sub.length()) ) )
            return i;
        return indexOf(str, sub, i+1);
}

Pesavo che fosse più leggibile con due indici.