[JAVA] problemi alberi binari

[fero86]

Originariamente inviato da malocchio

Concettualmente un albero è definito induttivamente, quale struttura migliore per esercitarsi nella scrittura di funzioni ricorsive?

non é solo un esercizio di stile, é anche questione di semplicitá del codice.

Comunque la vedo ostica trasformare una DFS da ricorsiva a iterativa

molto piu semplice di quanto pensi (vedi post di DanieleC88), anche se comunque piu complicato di un algoritmo ricorsivo.

Inoltre, statisticamente parlando penso possiamo dire che la profondità di un albero cresce logaritmicamente rispetto al numero dei nodi...

"statisticamente" non vuol dire niente: l'altezza di un albero é logaritmica nel numero di nodi se l'albero gode di una certa proprietá di bilanciamento come quella degli alberi AVL o quella degli alberi RB.

[banryu79]

Originariamente inviato da fero86

1) no se il linguaggio é tail-call optimized
2) early optimization is the root of all evil

1) Ok, ma il titolo del thread riporta [JAVA] e, a meno che non mi sia perso per strada qualcosa, questa ottimizzazione in Java non c'è.

2) Su questo sono d'accordo anche io, ma non intendevo sottointendere che è sempre meglio implementare i metodi di tree traversal in modo iterativo che ricorsivo, anche perchè non lo penso.

[oNaSsIs]

In generale si parla di ricorsione in coda (o tail recursive) quando una funzione f chiama al suo interno una funzione g (la quale può anche essere f stessa, come nel nostro caso) e il valore che restituisce è proprio quello restituito dalla funzione g, senza alcuna ulteriore computazione. Non è necessario quindi utilizzare un nuovo Record di Attivazione per g dato che f non deve mantenere alcun risultato intermedio, di conseguenza viene proprio utilizzato l'RdA di f per g. Quindi lo spazio utilizzato sullo stack è costante.

[banryu79]

Originariamente inviato da oNaSsIs

In generale si parla di ricorsione in coda (o tail recursive) quando una funzione f chiama al suo interno una funzione g (la quale può anche essere f stessa, come nel nostro caso) e il valore che restituisce è proprio quello restituito dalla funzione g, senza alcuna ulteriore computazione. Non è necessario quindi utilizzare un nuovo Record di Attivazione per g dato che f non deve mantenere alcun risultato intermedio, di conseguenza viene proprio utilizzato l'RdA di f per g. Quindi lo spazio utilizzato sullo stack è costante.

Grazie delle spiegazioni.
In ogni caso, qui si sta parlando di Java, e bisogna tenere in considerazione le implementazioni esistenti delle specifiche della Java Virtual Machine e del Bytecode.

Una cosa del genere:

public class TailCall
{
    private static int tailCallRecursion (int i, int times) {
        if (times <= 0) return i;
        return tailCallRecursion(i, times-1);
    }

    public static void main (String... argv) {
        int result = tailCallRecursion(0, 10000);
        System.out.println(result);
    }
}

se compilata e mandata in esecuzione provoca una java.lang.StackOverflowError.

[fero86]

Originariamente inviato da banryu79

1) Ok, ma il titolo del thread riporta [JAVA] e, a meno che non mi sia perso per strada qualcosa, questa ottimizzazione in Java non c'è.

be', il discorso stava prendendo un respiro piu generale.

Originariamente inviato da oNaSsIs

In generale si parla di ricorsione in coda (o tail recursive) quando una funzione f chiama al suo interno una funzione g (la quale può anche essere f stessa, come nel nostro caso) e il valore che restituisce è proprio quello restituito dalla funzione g, senza alcuna ulteriore computazione. Non è necessario quindi utilizzare un nuovo Record di Attivazione per g dato che f non deve mantenere alcun risultato intermedio, di conseguenza viene proprio utilizzato l'RdA di f per g. Quindi lo spazio utilizzato sullo stack è costante.

grazie per le delucidazioni

[malocchio]

Originariamente inviato da malocchio

Concettualmente un albero è definito induttivamente, quale struttura migliore per esercitarsi nella scrittura di funzioni ricorsive?
Comunque la vedo ostica trasformare una DFS da ricorsiva a iterativa
Inoltre, statisticamente parlando penso possiamo dire che la profondità di un albero cresce logaritmicamente rispetto al numero dei nodi...

Originariamente inviato da DanieleC88

Basta appoggiarsi alla struttura dati più appropriata: nel caso di una DFS (visita in-order, nel caso degli alberi) basta usare uno stack. Anzi, concettualmente bastano anche un paio di puntatori (però è macchinoso ).
Vedo più problematica la BFS (visita per livelli, nel caso degli alberi), ma anche là non è difficilissimo: basta usare una coda invece di uno stack.

Originariamente inviato da fero86

non é solo un esercizio di stile, é anche questione di semplicitá del codice.
molto piu semplice di quanto pensi (vedi post di DanieleC88), anche se comunque piu complicato di un algoritmo ricorsivo.
"statisticamente" non vuol dire niente: l'altezza di un albero é logaritmica nel numero di nodi se l'albero gode di una certa proprietá di bilanciamento come quella degli alberi AVL o quella degli alberi RB.

Da quello che ho capito l'autore del post si sta esercitando a lavorare su alberi con la ricorsione...

"statisticamente"... ho usato la parola sbagliata!

[oNaSsIs]

Originariamente inviato da banryu79

In ogni caso, qui si sta parlando di Java, e bisogna tenere in considerazione le implementazioni esistenti delle specifiche della Java Virtual Machine e del Bytecode.

Hai ragione, il codice da te scritto rispetta la definizione ma restituisce un eccezione di tipo stack overflow. Questa cosa incuriosisce anche me, non ho mai usato la ricorsione in coda con Java e mi sembra una grossa pecca la sua mancata implementazione. Cercherò di documentarmi, per ora ho trovato questo.

[fero86]

Originariamente inviato da oNaSsIs

Hai ragione, il codice da te scritto rispetta la definizione ma restituisce un eccezione di tipo stack overflow.

la solleva, non la restituisce, ed inoltre é un errore, non un'eccezione.

Questa cosa incuriosisce anche me, non ho mai usato la ricorsione in coda con Java e mi sembra una grossa pecca la sua mancata implementazione. Cercherò di documentarmi, per ora ho trovato questo.

piu che una grossa pecca é un trend: solitamente solo i linguaggi funzionali implementano questa ottimizzazione.

[oNaSsIs]

Chiedo venia per il mio linguaggio inappropriato...

[malocchio]

Originariamente inviato da fero86

la solleva, non la restituisce, ed inoltre é un errore, non un'eccezione.

Come siamo pignoli!

[banryu79]

Originariamente inviato da fero86

la solleva, non la restituisce, ed inoltre é un errore, non un'eccezione.
.

In Java le eccezioni non si "sollevano" (raise) ma si... lanciano! (throw)

Originariamente inviato da malocchio

Come siamo pignoli!

Non "pignoli", ma precisi.
E con questa ho vinto il premio rompicoglioni della domanica

[DanieleC88]

Originariamente inviato da banryu79

[...] della domanica

Si dice domenica.
Fregato il premio!

[banryu79]

Originariamente inviato da DanieleC88

Si dice domenica.
Fregato il premio!

...
Ma lol

[fero86]

D'OH