[JAVA] Metodo ricorsivo boolean aiuto

[Ingen2]

Ciao a tutti, devo imparare a scrivere metodi ricorsivi che restituiscono valori di tipo boolean.
Ho un problema a scrivere un metodo ricorsivo che riceve in input una stringa (ed altri parametri se servono) e restituisce true se il numero di caratteri minuscoli presenti nella stringa è pari.
Ecco il codice che ho impostato:
(Il primo valore di i che gli viene passato è s.length()-1)

private static boolean carattRic(String s, int i){
boolean esito=false;
int tot=0;
int n=s.length();

if(i==0){
if(Character.isLowerCase(s.charAt(0)))
esito=true;
else
esito=false;
 }
else{
for(int p=0; p<=i; p++){
if(Character.isLowerCase(s.charAt(p)))
tot++;}
esito=((tot%2==0)&&carattRic(s,i-1));
 }
return esito;
 }
}

Il problema è che, giustamente, quando un metodo trova un numero dispari di caratteri minuscoli mi da false e quindi ottengo solo false come esito.
Non so come scriverlo...perchè devo legare ogni valore di esito ad un metodo ad un altro metodo ricorsivo e ad una condizione!

[mone.java]

Per fare un metodo ricorsivo ti conviene procedere cosi:

1) Prima imposti la condizione di uscita, nel tuo caso si tratta di verificare che l'iesimo carattere sia dentro alla stringa

if (s.lenght() - 1 == i) {
   retrurn true;
}

poi dopo devi impostare la logica che consiste nel mettere in AND il valore dell'attuale carattere con quello restituito dal resto della stringa...

return Character.isLowerCase(s.charAt(0)) && carattRic(s, i++);

il metodo ,o chiamerai cosi:

carattRic("Stringa",0);

non ho testato il codice ma la logica comuqnue è questa...

EDIT:
Scusa ho letto adesso meglio e ho visto che si tratta di contare il numero di caratteri pari e restituisce true in caso siano pari (la mia restituisce true nel caso in cui siano tutti lowercase)... In tal caso non devi fare altro che aggiungere un parametro alla funzione che sarebbe il valore di ritorno e fare l check su quello! prova da solo se non riesci fammi sapere!

[Ingen2]

Intanto grazie per aver risposto, poi quello che ho in mente è di far invocare questo metodo da un main che gli passa la stringa dopo averla chiesta all'utente, in modo che la stringa in ingresso possa essere qualunque, ad esempio:

class Ricorsivo{

public static void main(String args[]){
InputWindow in=new InputWindow();
OutputWindow out=new OutputWindow();
String s=in.readString("Inserisci stringa");
int n=s.length();
out.write("Esito:"+carattRic(s,n-1));
 }

private static boolean carattRic(String s, int i){
boolean esito;
int tot=0;

if(i==0){
esito=false;
 }

else{
for(int p=0; p<=i; p++){
if(Character.isLowerCase(s.charAt(p)))
tot++;}
esito=((tot%2==0)&&carattRic(s,i-1));
 }
return esito;
 }
}

Come hai detto ho fissato la condizione di uscita, l'ho messa per i=0, quindi comincio da s.length()-1 e vado a scendere; poi l'ho corretto e l'ho messo false perchè se il carattere è uno solo per forza è dispari, poi per gli altri ho messo che il valore di ritorno dipenda dai precedenti con:

esito=((tot%2==0)&&carattRic(s,i-1));

il fatto è che (credo perchè il primo mi da false) visto che c'è AND anche tutti gli altri mi danno false.
Solo che ho provato a fargli dare true per i=0 (anche se non dovrebbe quindi), ma non funziona lo stesso, compilare compila ma poi quando esegue se gli do ad esempio:"aaaa" cioè un numero pari di caratteri minuscoli, mi da false comunque. Quindi l'errore deve stare da un'altra parta ma non capisco dov'è!

[sottovento]

Io mi terrei sul semplice:

    public static boolean isEven(String s)
    {
        int l;
        if ((l = s.length()) == 0)  /* Caso base: stringa vuota. In tal caso, e' pari */
            return true;
        if (l == 1)  /* Caso base: stringa di un carattere. In tal caso, se il carattere e' minuscolo e' dispari */
            return !Character.isLowerCase(s.charAt(0));

        /* passo ricorsivo: divido in due la stringa e controllo le singole parti. Se entrambi sono pari o dispari, il risultato e' pari */
        /* Potrei non dividere in due e controllare un carattere ed il rimanente, ma mi piaceva cosi' */
        boolean a = isEven(s.substring(0,l/2));
        boolean b = isEven(s.substring(l/2));
        return (a && b) || (!a && !b);
    }

[mone.java]

class Ricorsivo {

    public static void main(String args[]) {
        String s = "pariPARI";
        System.out.println("Esito:" + carattRic(s, s.length() - 1, 0));
        s = "dispariDISPARI";
        System.out.println("Esito:" + carattRic(s, s.length() - 1, 0));
    }

    private static boolean carattRic(String s, int i, int tot) {
        tot += Character.isLowerCase(s.charAt(i)) ? 1 : 0;

        if (i == 0) {
            return (tot % 2 == 0);
        } else {
            return carattRic(s, --i, tot);
        }
    }
}

EDIT:
La soluzione di sottovento è molto interessante dal punto di vista algoritmico!

[sottovento]

Originariamente inviato da mone.java

EDIT:
La soluzione di sottovento è molto interessante dal punto di vista algoritmico!

Beh dai, non e' niente di che. Non fraintendermi, non sto criticando, ma trovo che doversi trascinare un paio di parametri in piu' renda le cose piu' difficili.
D'altronde il problema non era quello di contare i caratteri minuscoli ma di stabilire se il loro numero era pari o dispari, e questo puo' essere fatto piu' facilmente, no?

[mone.java]

Originariamente inviato da sottovento

Beh dai, non e' niente di che. Non fraintendermi, non sto criticando, ma trovo che doversi trascinare un paio di parametri in piu' renda le cose piu' difficili.
D'altronde il problema non era quello di contare i caratteri minuscoli ma di stabilire se il loro numero era pari o dispari, e questo puo' essere fatto piu' facilmente, no?

Dicevo che il tuo è interessante dal punto di vita algoritmico perchè usa divite et impera che comunque è un approccio interessante ai problemi, indipendentemente dal fatto che io preferissi un'altra soluzione. Quando facevo io l'università e ci facevano fare la ricorsione con scheme facevo prima il metodo con gli n parametri e poi l'overload he semplicemente nascondeva i parametri ijn pi... questione di abitudine

[banryu79]

return (a && b) || (!a && !b);

può essere sintetizzata nell'equivalente:

return a == b;

[sottovento]

Originariamente inviato da banryu79

può essere sintetizzata nell'equivalente:

return a == b;

Sono un pollo. Non per niente volo sottovento

Quindi il metodo diventa:

public static boolean isEven(String s){
    int l = s.length();
    return (l == 0) ? true : (l == 1) ?  !Character.isLowerCase(s.charAt(0)) : isEven(s.substring(0,l/2)) == isEven(s.substring(l/2));
}

[Ingen2]

Grazie per le risposte!
Con le stringhe adesso mi più chiaro, ma vorrei chiedervi un'altra cosa se possibile:
Se volessi creare un metodo ricorsivo che restituisce true se la somma degli elementi di un array (ad esempio di interi) è pari, si potrebbe scrivere qualcosa di simile al caso della stringa?

Ho provato a scriverlo ma non mi è venuto niente di meglio:

private static boolean ricorsivo(int[] a, int i){
boolean esito;
int n=a.length;
int somma=0;

if(n==0)
esito=true;
else{

if(i==n-1){
for(int j=0; j<=i; j++)
somma+=a[j];
esito=(somma%2==0);}

else
esito=ricorsivo(a,i+1);
  }
return esito;
  }

La ricorsione c'è poco perchè serve solo per arrivare al caso i=n-1 per il quale si fa la somma...vorrei trovare una soluzione "più ricorsiva"...

[mone.java]

Originariamente inviato da Ingen2

Grazie per le risposte!
Con le stringhe adesso mi più chiaro, ma vorrei chiedervi un'altra cosa se possibile:
Se volessi creare un metodo ricorsivo che restituisce true se la somma degli elementi di un array (ad esempio di interi) è pari, si potrebbe scrivere qualcosa di simile al caso della stringa?

Ho provato a scriverlo ma non mi è venuto niente di meglio:

private static boolean ricorsivo(int[] a, int i){
boolean esito;
int n=a.length;
int somma=0;

if(n==0)
esito=true;
else{

if(i==n-1){
for(int j=0; j<=i; j++)
somma+=a[j];
esito=(somma%2==0);}

else
esito=ricorsivo(a,i+1);
  }
return esito;
  }

La ricorsione c'è poco perchè serve solo per arrivare al caso i=n-1 per il quale si fa la somma...vorrei trovare una soluzione "più ricorsiva"...

Stai sbagliando completamente approccio... quel for non deve esistere altrimenti la ricorsività non ha senso. Quello che devi fare (prendi spuno dagli esempi sopra) è valutare ad ogni passo della ricorsione l'n-esimo elemento dell'array (oppure l'n-1 esimo dipende se parti dalla cima o dal fondo). Quindi ogni volta che fai la chiamata ricorsiva devi passare l'input attuale meno l'elemento valutato.. Ovviamente potremmo metterti la soluzione anche di questo esercizio ma non impareresti molto. Intanto parti eliminando il ciclo for, in genere nelle funzioni ricorsive non si dovrebbero vedere cicli for in quanto il ciclo è ottenuto attraverso le chiamate ricorsive!

[Ingen2]

Allora non potendo pensare di dividere l'array(?) ho riscritto così il metodo, che sembra funzionare:

private static boolean ricorsivo(int[] a, int i, int numdispari) {

if(a.length==0)
return true;

  if(a[i]%2==0)
  numdispari=numdispari;
  else
  numdispari++;

if (i==0)
return (numdispari%2==0);
else
return ricorsivo(a, i-1, numdispari);

 }

Quindi come avevi fatto per le stringhe...non potendo dichiarare una variabile da far eventualmente incrementare ogni volta che si fa un chiamata ricorsiva, ti porti dietro il suo valore ogni volta che invochi un nuovo metodo e poi il check lo fai alla fine (cioè quando conta) il cui risultato rappresenta anche il caso base; è corretto?

[mone.java]

NOn ho controllato se la funzione è precisa ma cmq è giusto quello che dici... se poi facendo i test funziona allora è perfetto.. Un alternativa alla soluzione con i parametri è usare una mtodologia come quella esposta da sottovento.. ma secondo me è un po più complicato...

[sottovento]

Stavolta il tuo metodo deve avere un paio di parametri in piu': il punto di partenza all'interno dell'array e la lunghezza della porzione dell'array interessato.
Il motivo e' semplice: nell'implementazione fatta con le stringhe, la substring() creava ogni volta una stringa nuova con le dimensioni corrette. Quindi ad ogni ricorsione si creavano delle stringhe nuove. Pero' tutto era fatto dalla substring() quindi era semplice da scrivere (sebbene, ovviamente, sia stato ben poco efficiente).
Puoi usare lo stesso criterio anche in questo caso; tuttavia, non volendo duplicare tutte le volte l'array, potresti scrivere:

    public static boolean isEven(int[] vect, int startIndex, int length)
    {
        if (length == 0)
            return true;
        if (length == 1)
            return (vect[startIndex] % 2) == 0;
        return ((vect[startIndex] % 2) == 0) == isEven(vect, startIndex+1, length-1);
    }

Ovviamente in ingresso alla ricorsione gli devi passare 0 come startIndex ed il numero iniziale degli elementi come length; per esempio:

    public static void main(String[] args)
    {
        int[][] arrVect = 
        {
            { 1 },
            { 2 },
            { 1, 2},
            { -1, 2, 3},
            { 1, 2, 3, 4, 5, 6, 7}
        };

        for (int[] vect : arrVect)
            System.out.println ("pari = " + isEven(vect, 0, vect.length));
    }

[Ingen2]

Grazie di nuovo a tutti, questi giorni ho provato a scrivere parecchi metodi ricorsivi utilizzando i consigli che mi avete dato, li ho testati e funzionano bene. Tutti metodi abbastanza semplici, però vabè xD Grazie ancora!