Java e metodo ricorsivo

[alex170]

ciao a tutti! devo creare un metodo ricorsivo che calcola la frequenza del carattere c nella stringa s. La frequenza deve essere calcolata non creando nuove stringhe.
La prima cosa che mi viene in mente è:

public static int frequenza(String s, char c) {
    int f; 
if (s.length()==0) 
     f = 0; 
else{ 
     if (s.charAt(0)==c)
         f = 1 + frequenza(s.substring(1),c); 
     else
         f = frequenza(s.substring(1),c);
} 
return f; 
}

però così creo delle stringhe che sono sottostringhe di s....come posso fare?

[Ska1]

potresti aggiungere un parametro in più alla lista dei parametri formali, che ti rappresenta l'indice da considerare in quella chiamata ricorsiva:

public static int freq(String s, char c, int index) {
  if (s.length() == 0) return 0;
  if (s.charAt(index) == c) return 1 + freq(s, c, index + 1);
  else return freq(s,c,index + 1);
}

[apatriarca]

La condizione di terminazione della funzione ricorsiva è sbagliata. Siccome la tua stringa non viene modificata dalla funzione, la sua lunghezza rimarrà invariata e la condizione sarà sempre vera (assumendo che la stringa non sia di lunghezza zero fin dalla prima chiamata). La tua funzione terminerà con un eccezione. Il metodo corretto è quello di verificare che l'indice sia minore della dimensione, cioè:

public static int freq(String s, char c, int index) { 
  if (index >= s.length()) return 0; 
  if (s.charAt(index) == c) return 1 + freq(s, c, index + 1); 
  else return freq(s,c,index + 1); 
} 

[Ska1]

Ops , troppa distrazione

[alex170]

interessante...però è l'esercizio che definisce il metodo con quei parametri formali. Se non potessi cambiarlo, come potrei risolvere?

[edge1]

		
		
class prova {
	public static int fre(String s,char c)
{
	
		try
			{
				
				if (s.charAt(a++)==c) return(1+fre(s,c)); 
				return ( fre(s,c));
				
		        }
	
		catch(Exception e) {a=0; return 0;}
}
	
	static int a=0;
public static void main(String args[])
{
	int a=fre("cicc",'c');
	System.out.println(a);
}
}

[apatriarca]

Normalmente si definiscono due metodi:

public static int freq(String s, char c) {
    return freq(s, c, 0);
}

public static int freq(String s, char c, int index) { 
  if (index >= s.length()) return 0; 
  if (s.charAt(index) == c) return 1 + freq(s, c, index + 1); 
  else return freq(s,c,index + 1); 
}

[edge1]

Se non può aggiungere parametri deve sfruttare le eccezioni e catturarla come caso base della funzione come ho scritto sopra.

[apatriarca]

"edge":Se non può aggiungere parametri deve sfruttare le eccezioni e catturarla come caso base della funzione come ho scritto sopra.

Si tratta invece, secondo me, di un pessimo metodo per implementare questa funzione ricorsiva per le seguenti ragioni:
1. Usi le eccezioni per controllare la logica del programma quando dovrebbero essere principalmente usate per la verifica degli errori. Se non correttamente commentato può creare confusione in chi, come me, è abituato ad ignorare il codice di gestione delle eccezioni quando cerco di comprendere il funzionamento di una funzione. Per me le eccezioni vanno usate per gestire casi eccezionali, che normalmente non dovrebbero accadere e non qualcosa che accadrà di sicuro. Nel tuo codice è comunque inutile usare le eccezioni. È la variabile statica a che hai introdotto che elimina la necessità di avere un ulteriore parametro e non l'uso delle eccezioni. Il seguente codice usa infatti un semplice if:

class Prova {

    public static int freq(String s, char c) { 
        if (index >= s.length()) {
            index = 0;
            return 0;
        } else if (s.charAt(index) == c) {
            ++index;
            return 1 + freq(s, c);
        } else {
            return freq(s, c);
        } 
    } 

    private static int index = 0;

    public static void main(String args[]) {
        int a=fre("cicc",'c'); 
        System.out.println(a); 
    } 
}

2. Il tuo metodo funziona quando il programma viene eseguito in un singolo processore, ma se più thread tentassero di eseguire freq in contemporanea avresti due metodi che scrivono sulla variabile index in contemporanea e quindi un risultato errato in entrambe le chiamate.

Il metodo che ho scritto in precedenza è quello che viene comunemente usato nei linguaggi funzionali dove le funzioni ricorsive sono la norma (magari usando una lambda) ed è corretto anche in quei casi in cui non è possibile fare affidamento ad una variabile statica (in effetti i linguaggi funzionali non permettono la memorizzazione di uno stato). Il secondo metodo freq andava solo dichiarato private (è stata una svista nel codice che ho postato nel post precedente).

[edge1]

Non ho nulla da obbiettare sul tuo codice,ma..

2. Il tuo metodo funziona quando il programma viene eseguito in un singolo processore, ma se più thread tentassero di eseguire freq in contemporanea avresti due metodi che scrivono sulla variabile index in contemporanea e quindi un risultato errato in entrambe le chiamate.

Va da se che utilizzerei la funzione in mutua esclusione.

[apatriarca]

"edge":Va da se che utilizzerei la funzione in mutua esclusione.

Non mi sembra una cosa semplicissima considerando che la funzione deve richiamare se stessa prima di terminare la propria esistenza.

[alex170]

"edge":

class prova {
   public static int fre(String s,char c)
{
   
      try
         {
            
            if (s.charAt(a++)==c) return(1+fre(s,c));
            return ( fre(s,c));
            
              }
   
      catch(Exception e) {a=0; return 0;}
}
   
   static int a=0;
public static void main(String args[])
{
   int a=fre("cicc",'c');
   System.out.println(a);
}
}

questo codice non lo potrei usare perchè le ruzioni try e catch non le ho studiate, non fanno parte del mio programma...

"apatriarca":

public static int freq(String s, char c) {
    return freq(s, c, 0);
}

public static int freq(String s, char c, int index) {
  if (index >= s.length()) return 0;
  if (s.charAt(index) == c) return 1 + freq(s, c, index + 1);
  else return freq(s,c,index + 1);
} 

nemmeno questo potrei usare perchè cado ad inserire un ulteriore parametro formale quando lo schelet della classe ce l'ho già definito dall'esercizio...

"apatriarca":

class Prova {

    public static int freq(String s, char c) {
        if (index >= s.length()) {
            index = 0;
            return 0;
        } else if (s.charAt(index) == c) {
            ++index;
            return 1 + freq(s, c);
        } else {
            return freq(s, c);
        }
    }

    private static int index = 0;

    public static void main(String args[]) {
        int a=fre("cicc",'c');
        System.out.println(a);
    }
}

questo già mi garba di più ma c'un metodo che nel mio scheletro non c'è...

[edge1]

che metodo?

[alex170]

scusami, non un metodo, ma la variabile di classe:

private static int index = 0

[edge1]

Ma come è il tuo scheletro?

[alex170]

class GestioneStringhe{

    /* restituisce la frequenza del carattere c nella stringa s usando il metodo ricorsivo frequenzaRic(char c, String s, int p)*/
    public static int frequenza (String s, char c){…}

    /* restituisce l’esito della relazione d’ordine lessicografico sulle stringhe s e t usando il metodo ricorsivo confrontaRic(String s, String t, int p)*/
   public static int confronta (String s, String t){…}

   /* metodo ricorsivo che calcola la frequenza del carattere c nella stringa s. La frequenza viene calcolata non creando nuove stringhe*/
   private static int frequenzaRic (String s, char c, int p){…}
   
   /* metodo ricorsivo che confronta le stringhe s e t. Il confronto lessicografico viene determinato non creando nuove stringhe*/
   private static int confrontaRic (String s, String t, int p){…}
}

[Ska1]

Direi che i commenti ai metodi sono chiari, "frequenza" chiama il metodo ricorsivo "frequenzaRic" che proprio ha tre parametri di cui l'ultimo un intero "p" che corrisponde al famoso index....

[edge1]

8 mesi di discussione e poi il parametro index c'era.

[alex170]

che imbecille! scusate tanto e grazie dell'aiuto!!!