[Java] Tramutare una funzione iterativa in ricorsiva

[angelotm]

innanzitutto spero di aver azzeccato il titolo della discussione
volevo sapere se qualcuno di voi riesce ad aiutarmi a trasformare questa funzione in ricorsiva:

    private nodo check_posizione(persona nuova){
        nodo precedente, successivo, posizione;
        precedente=start;
        successivo=start;
        posizione=start;
        if(check_cognome(nuova,start)<0){posizione=null;return posizione;}
        else if(check_cognome(nuova,start)==0){
            if(check_nome(nuova,start)<=0){posizione=null;return posizione;}
            else{
                successivo=start.link;
                while(successivo!=null && check_cognome(nuova,successivo)==0){
                    if(check_nome(nuova,successivo)<=0){posizione=precedente;return posizione;}
                    else{precedente=successivo;successivo=successivo.link;}
                }
                if(successivo==null || check_cognome(nuova,successivo)!=0){posizione=precedente;return posizione;}
            }
        }
        else{
            precedente=successivo;
            successivo=start.link;
            while(successivo!=null && check_cognome(nuova,successivo)>0){
                precedente=successivo;
                successivo=successivo.link;
            }
            if(successivo==null || check_cognome(nuova,successivo)<0){posizione=precedente;return posizione;}
            else if(check_cognome(nuova,successivo)==0){
                if(check_nome(nuova,successivo)<=0){posizione=precedente;return posizione;}
                else{
                    precedente=successivo;
                    successivo=successivo.link;
                    while(successivo!=null && check_cognome(nuova,successivo)==0){
                        if(check_nome(nuova,successivo)<=0){posizione=precedente;return posizione;}
                        else{precedente=successivo;successivo=successivo.link;}
                    }
                    if(successivo==null || check_cognome(nuova,successivo)!=0){posizione=precedente;return posizione;}
                    else{posizione=precedente;return posizione;}
                }
            }
        }
        return posizione;
    }

le funzioni check_nome() e check_cognome() se ve lo state chiedendo restituiscono un intero che determina se il cognome viene prima o dopo

        
    private int check_nome(persona nuova, nodo successivo){
        return nuova.nome.compareTo(successivo.info.nome);
    }
    
    private int check_cognome(persona nuova, nodo successivo){
        return nuova.cognome.compareTo(successivo.info.cognome);
    }

ecco ora se leggete la funzione check_posizione() vi rendete conto che controlla il cognome, e in base al cognome (se e' uguale) controlla il nome.
ora, considerando che la funzione e' gia' bella lunghetta solo controllando per cognome e nome, dovrei controllare anche per anno e per altri dati, potrei continuare a implementare condinzioni ma voglio ridimensionare il tutto rendendola ricorsiva, tipo check_posizione(dato) dove dato e' il campo da controllare (cognome, nome, anno, etc)
in modo che ad esempio quando il cognome risulta uguale io faccia una cosa del genere:
if(check_cognome(nuova,successivo)==0){check_posiz ione(nome);}
qualcuno di voi ha qualche idea?
perche' non riesco a venirne fuori sinceramente!
se avete altre soluzioni o consigli sul codice e' tutto ben accetto
grazie, angelo

EDIT: in realta' ci ho gia' provato, ma non riesco a passare come parametro alla funzione una sorta di "stringa" del tipo:

private nodo check_posizione(persona nuova){
        ...
        if(check(nuova,start,nome)
        oppure
        if(check(nuova,start,cognome)
}

private int check(persona nuova, nodo successivo, String dato){
        return nuova.nome.compareTo(successivo.info.dato);
    }

la parte in rosso, ovviamente, e' sbagliata perche' cerca un campo successivo.info.dato che non esiste (non avendo dichiarato String dato), dato dovrebbe solo servire per scegliere quale campo controllare!!

[andbin]

Originariamente inviato da angelotm
volevo sapere se qualcuno di voi riesce ad aiutarmi a trasformare questa funzione in ricorsiva:

Motivo del volerla fare ricorsiva? Ti è stato chiesto/imposto? Perché se si tratta di una lista linkata che potenzialmente è molto lunga, la ricorsione non è una buona soluzione.

Originariamente inviato da angelotm
ora, considerando che la funzione e' gia' bella lunghetta

Oltre che "fumosa", direi ...

Vediamo di chiarire (e verifica quanto dico ora):
- Hai una lista linkata in cui i nodi hanno come "valore" un oggetto persona, giusto?
- La lista è ordinata/da tenere ordinata, giusto?
- Il criterio di ordinamento è per cognome e se uguale per nome, giusto?
- Devi trovare il punto (nodo precedente per l'inserimento) in cui inserire un nuovo nodo in modo che resti ordinato secondo quanto detto sopra, giusto?

[angelotm]

Originariamente inviato da andbin
Vediamo di chiarire (e verifica quanto dico ora):
- Hai una lista linkata in cui i nodi hanno come "valore" un oggetto persona, giusto?
- La lista è ordinata/da tenere ordinata, giusto?
- Il criterio di ordinamento è per cognome e se uguale per nome, giusto?
- Devi trovare il punto (nodo precedente per l'inserimento) in cui inserire un nuovo nodo in modo che resti ordinato secondo quanto detto sopra, giusto?

ciao e grazie per la risposta innanzitutto!
- si ho una lista linkata (creata da me pero'!) dove i nodi hanno 2 campi, un campo persona (che e' una classe con vari parametri, quali appunto cognome nome etc, ed un campo nodo che si riferisce al successivo.
- la lista e' si' ordinata ed e' da tenere ordinata proprio grazie alla funzione che ho scritto!
in quanto restituisce il nodo precedente a dove va' collocato quello nuovo!
- il criterio di ordinamento e' quello che hai detto tu, ovvero cognome->nome->anno->etc
- il punto dove inserire il nuovo nodo in modo che resti ordinato e' il valore che restituisce la funzione check_posizione(persona nuova)

hai idee a riguardo?

[andbin]

Originariamente inviato da angelotm
- si ho una lista linkata (creata da me pero'!) dove i nodi hanno 2 campi, un campo persona (che e' una classe con vari parametri, quali appunto cognome nome etc, ed un campo nodo che si riferisce al successivo.
- la lista e' si' ordinata ed e' da tenere ordinata proprio grazie alla funzione che ho scritto!
in quanto restituisce il nodo precedente a dove va' collocato quello nuovo!
- il criterio di ordinamento e' quello che hai detto tu, ovvero cognome->nome->anno->etc
- il punto dove inserire il nuovo nodo in modo che resti ordinato e' il valore che restituisce la funzione check_posizione(persona nuova)

hai idee a riguardo?

Bene allora:

1) Crea un metodo che dati 2 oggetti persona li compara secondo cognome/nome e restituisce 0, >0, <0. Ti sconsiglio di spezzare la cosa come hai fatto finora.

2) Per cercare il nodo dietro cui inserire il nuovo nodo, allora innanzitutto devi gestire il caso "speciale" di inserimento prima della "testa".
Comunque tieni 2 variabili: il nodo "corrente" (inizialmente = alla testa) e un nodo "precedente" (inizialmente a null).
Cicla finché corrente è diverso da null. Compara la persona del nodo con la persona da aggiungere. Se quella del nodo è maggiore di quella da aggiungere, hai trovato il punto precedente, esci subito dal ciclo.
Altrimenti nel corpo del ciclo che prosegue: aggiorni il precedente con quello corrente e fai avanzare corrente.
Dopo il ciclo, crei il nuovo nodo e poi hai solo da gestire o il caso speciale (prima della testa) o il caso normale (dopo un nodo esistente, testa compresa).

Io ho provato a scriverlo qualche minuto fa. Il metodo aggiungi della mia lista è di una banalità e linearità rispetto al tuo (fumoso) metodo che probabilmente neanche ti immagini!

Valuta quanto ho detto e prova a farlo meglio. Se hai dubbi, chiedi ovviamente.

[angelotm]

1) Crea un metodo che dati 2 oggetti persona li compara secondo cognome/nome e restituisce 0, >0, <0. Ti sconsiglio di spezzare la cosa come hai fatto finora.

perdona la mi ignoranza, io creo un metodo in cui faccio cognome.compareTo(cognome2) e nello stesso metodo un'altra istruzione che fa' nome.compareTo(nome2), e alla fine quale restituisco?

2) Per cercare il nodo dietro cui inserire il nuovo nodo, allora innanzitutto devi gestire il caso "speciale" di inserimento prima della "testa".
Comunque tieni 2 variabili: il nodo "corrente" (inizialmente = alla testa) e un nodo "precedente" (inizialmente a null).
Cicla finché corrente è diverso da null. Compara la persona del nodo con la persona da aggiungere. Se quella del nodo è maggiore di quella da aggiungere, hai trovato il punto precedente, esci subito dal ciclo.
Altrimenti nel corpo del ciclo che prosegue: aggiorni il precedente con quello corrente e fai avanzare corrente.
Dopo il ciclo, crei il nuovo nodo e poi hai solo da gestire o il caso speciale (prima della testa) o il caso normale (dopo un nodo esistente, testa compresa).

con questo mi trovo perfettamente, e' quello che ho fatto io fin'ora
prima gestisco il caso in cui va' inserito in testa, poi ciclo fino a trovare la posizione se non si trova in testa finche' arriva in fondo e aggiungo alla fine.

solo se puoi delucidarmi un po' piu' in dettaglio riguardo la funzione che riceve 2 oggetti persona e li compara per favore
grazie dell'aiuto comunque!!
angelo

[angelotm]

andbin ho risolto
ho seguito il tuo consiglio e mi sn inventato una cosa hehe :P
ecco come ho risparmiato 50righe:

    private nodo check_posizione(persona nuova){
        nodo precedente=null, successivo=start ;
        while(successivo!=null && check("cognome",nuova,successivo)>0){precedente=successivo;successivo=successivo.link;}
        while(successivo!=null && check("cognome",nuova,successivo)==0){
            while(successivo!=null && check("cognome",nuova,successivo)==0 && check("nome",nuova,successivo)>0){precedente=successivo;successivo=successivo.link;}
            while(successivo!=null && check("cognome",nuova,successivo)==0 && check("nome",nuova,successivo)==0){
                while(successivo!=null && check("cognome",nuova,successivo)==0 && check("nome",nuova,successivo)==0 && check("anno",nuova,successivo)>0){precedente=successivo;successivo=successivo.link;}
                return precedente;
            }
            return precedente;
        }
        return precedente;
    }
    
    private int check(String dato, persona nuova, nodo successivo){
        if ("cognome".equals(dato)){return nuova.cognome.compareTo(successivo.info.cognome);}
        else if("nome".equals(dato)){return nuova.nome.compareTo(successivo.info.nome);}
        else if("anno".equals(dato)){
            if(nuova.anno>successivo.info.anno){return 1;}
            else if(nuova.anno==successivo.info.anno){return 0;}
            else{return -1;}}
    return 0;
    }

grazie mille per i consigli e la pazienza
angelo

[andbin]

Originariamente inviato da angelotm
andbin ho risolto
ho seguito il tuo consiglio e mi sn inventato una cosa hehe :P
ecco come ho risparmiato 50righe:

Ehm ... no mi dispiace ma non ci siamo affatto. Già quando ho visto quei 5 while in fila mi si stavano incrociando gli occhi .... quando poi ho visto che hai "tipizzato" il check passando una stringa "cognome" o "nome" ... qui mi stava per prendere un "coccolone".

Se vuoi fare le cose bene e specialmente se quello che stai facendo è un "esercizio" didattico che dovrai presentare e vuoi fare bella figura ..... ti sconsiglio di continuare con quel codice.

[angelotm]

Originariamente inviato da andbin
Ehm ... no mi dispiace ma non ci siamo affatto. Già quando ho visto quei 5 while in fila mi si stavano incrociando gli occhi .... quando poi ho visto che hai "tipizzato" il check passando una stringa "cognome" o "nome" ... qui mi stava per prendere un "coccolone".

Se vuoi fare le cose bene e specialmente se quello che stai facendo è un "esercizio" didattico che dovrai presentare e vuoi fare bella figura ..... ti sconsiglio di continuare con quel codice.

nuoooo
e come mi consigli di fare allora?
questo e' l'unico escamotage(non so come si scrive!) che ho trovato.. sono tutto orecchie comunque!
ah comunque non e' un esercizio didattico, sto imparando java da autodidatta

[andbin]

Originariamente inviato da angelotm
sono tutto orecchie comunque!
ah comunque non e' un esercizio didattico, sto imparando java da autodidatta

Visto che non è un esercizio che devi presentare, allora in questo caso mi permetto di mostrarti la "mia" implementazione.

TestListaPersoneOrdinata.java

public class TestListaPersoneOrdinata {
    public static void main(String[] args) {
        ListaPersone lista = new ListaPersone();

        lista.aggiungi(new Persona("Verdi", "Elena"));
        lista.aggiungi(new Persona("Rossi", "Mario"));
        lista.aggiungi(new Persona("Verdi", "Roberto"));
        lista.aggiungi(new Persona("Ferrari", "Giorgia"));
        lista.aggiungi(new Persona("Bianchi", "Simone"));
        lista.aggiungi(new Persona("Rossi", "Carlo"));
        lista.aggiungi(new Persona("Bianchi", "Giulia"));
        lista.aggiungi(new Persona("Ferrari", "Luca"));

        lista.stampa();
    }
}


class ListaPersone {
    private NodoPersona testa;

    public void aggiungi(Persona personaDaInserire) {
        NodoPersona corrente = testa;
        NodoPersona precedente = null;

        while (corrente != null) {
            if (comparaPersone(corrente.persona, personaDaInserire) > 0) {
                break;
            }

            precedente = corrente;
            corrente = corrente.successivo;
        }

        NodoPersona nuovoNodo = new NodoPersona();
        nuovoNodo.persona = personaDaInserire;

        if (precedente == null) {
            // Aggiunge in testa, prima del 1° nodo (se esiste) o se non ci sono nodi
            nuovoNodo.successivo = testa;
            testa = nuovoNodo;    // Il nuovo nodo È la testa!
        } else {
            // Aggiunge dopo il nodo 'precedente'
            nuovoNodo.successivo = precedente.successivo;
            precedente.successivo = nuovoNodo;
        }
    }

    public void stampa() {
        NodoPersona corrente = testa;

        while (corrente != null) {
            System.out.println(corrente.persona);
            corrente = corrente.successivo;
        }
    }

    private int comparaPersone(Persona p1, Persona p2) {
        int r = p1.getCognome().compareTo(p2.getCognome());

        if (r == 0) {
            r = p1.getNome().compareTo(p2.getNome());
        }

        return r;
    }

    private static class NodoPersona {
        private Persona persona;
        private NodoPersona successivo;
    }
}


class Persona {
    private String cognome;
    private String nome;

    public Persona(String cognome, String nome) {
        this.cognome = cognome;
        this.nome = nome;
    }

    public String getCognome() {
        return cognome;
    }

    public String getNome() {
        return nome;
    }

    public String toString() {
        return cognome + " " + nome;
    }
}

[angelotm]

nooooooooooo nn sono mai volgare quindi metto gli asterischi.. :P
***** sei un genio!! beh certo hai anche tanta esperienza
non avevo pensato che, in questa funzione:

    private int comparaPersone(Persona p1, Persona p2) {
        int r = p1.getCognome().compareTo(p2.getCognome());

        if (r == 0) {
            r = p1.getNome().compareTo(p2.getNome());
        }

        return r;
    }

effettivamente se restituisco il valore dopo aver confrontato il nome non me ne faccio piu' niente del valore del cognome! il valore del nome comprendera' anche quello del cognome!!
no davvero sei un genio!
dispendio di energia ZERO!!
davvero sei stato utilissimo!! finalmente capisco cosa intendevi con il creare una funzione che compara sia il cognome che il nome!
per verificare anche l'anno di nascita etcetera basta che nidifico gli if e restituisco il valore dell'anno!
sono davvero sbalordito! credimi!!
non so come ringraziarti :P
ma permettimi di approfittare del tuo genio e della tua esperienza per una domanda.. ^^
nell'escamotage che ho trovato io mi puoi spiegare cortesemente:
- il valore stringa che passo alla funzione per scegliere quale valore ottenere perche' e' cosi' "assurdo"
- e i cicli while nidificati perche' ti "impressionano" tanto (immagino per il dispendio di tempo e dati che devi analizzare il programma per restituire)

infine lascia che ti ringrazi almeno altre mille volte per l'aiuto che mi hai fornito!
e' davvero una lezione di vita, anzi di programmazione(!!), e una lezione che arricchisce il mio "problem solving" in programmazione!
grazie ancora!!
angelo

EDIT:
inoltre non avevo valutato che nella "comparazione" delle stringhe

r = p1.getNome().compareTo(p2.getNome());

e' inutile che vada a fare p1.info.cognome ma semplicemente richiamare la funzione che me lo restituisce!
c'é sempre da imparare!! fortuna che esistono persone come te che mi "allertano" sulle mie malefatte e su come ottimizzare il lavoro^^