Comments for post Le basi della ricorsione
Sabrina writes: ciao!
io nei prossimi mesi dovrò sostenere l'esame di algoritmi e strutture dati, incentrato in particolare sulla ricorsione.
ho un dubbio.
molti miei colleghi applicano la ricorsione in modo meccananico senza comprendere veramente come funzione l'algoritmo proposto. cioè applicano le regole.
io invece perdo prima un pò di tempo a cercare di capire come funzione il tutto senza ricorsione e poi la applico.
secondo voi applicare solo le regole base può bastare?
e se si, potreste farmi degli esempi macro a cui si può ricondurre ogni esercizio?
grazie enormemente.
Gin_Phreaks writes: un buon esempio e articolo sulla ricorsione:
http://www.autistici.org/ermes/index.php?pag=1&post=25
Jack writes: Confermo sulla tail recursion! Anche in C esiste, e in pratica attraverso tale tecnica di programmazione si elimina il bisogno di aprire mille stack di attivazione. In sostanza è un programma ricorsivo con l'efficienza di un programma iterativo.
Fra_T writes: >> Gli ultimi problemi li ho a
>> farmi ritornare l'array dalla
>> funzione ma ormai ci sono quasi ;)
Per lo stesso problema o usato array_merge... ci sarà una soluzione migliore, ma non la conosco :D
antirez writes: @FraT: @neon: il problema dell'ordinamento lo risolvete meglio se lo scomponete in due sottoproblemi diversi, il primo dei quali e': scrivere una funzione ricorsiva che dato una lista in input restituisce in output il suo elemento minore e il resto della lista.
Nel fine settimana comunque arrivano le soluzioni :)
neon writes: Ecco adesso credo di esserci vicino, non conoscevo la funzione array_search() per trovare la key del valore min (o max).
Al momento sono arrivato a trovare questa soluzione: cerco il valore min nell'array, se è diverso dal primo li scambio e poi continuo con il resto dell'array senza il primo valore. In questo modo non dovrebbero esserci problemi neanche con i valori ripetuti. Gli ultimi problemi li ho a farmi ritornare l'array dalla funzione ma ormai ci sono quasi ;)
Fra_T writes: iseven!! non ci avevo pensato così... bella soluzione :)
antirez writes: @neon: Ottimo per iseven! Un numero e' pari se il suo precedente non lo e' :) anche se io avrei scritto if ($x == 1) return false. E' esattamente identico ma mi sembra piu' matematicamente corretto.
Non e' strano che la funzione di ordinamento somiglia a quella di Fra_T! Anche io ho usato la stessa logica, e' il modo naturale di esprimere tramita la ricorsione un sacco di problemi, e' anche un po' come faresti a mano. Prendi l'elemento piu' grande e lo metti a sinistra. Poi cerchi quello piu' grande tra i rimanenti e lo metti subito dopo, e cosi' via :)
neon writes: La funzione iseven() finale di Fra_T contiene un check in più.
function iseven($x)
{
if($x == 0) return true;
return !iseven($x-1);
}
La seconda l'ho fatta praticamente allo stesso modo, aggiungendo solo il controllo di array vuoto.
La cosa strana è che la terza l'ho fatta anche uguale alla sua... basandomi unicamente sul tuo esempio con maxval().
(c'è un errore nel primo esempio s/end/stop/)
Se ho tempo ci ragiono ancora su, volevo risolverla prima dei tuoi risultati :P
antirez writes: Fabrizio: grazie mille! sei troppo buono. Riguardo a memoize mi sa che ho una versione piu' veloce e performante in cantiere :) Ci ho pensato l'altro giorno e ho dimenticato di implementarla ma ora che me ne sono ricordato grazie a te la segno nella TODO list.
Fabrizio writes: non entro nel tecnicismo ma voglio segnalare la mia stima per questi post! Un grande! :)
Senza considerare che molti dei tuoi suggerimenti poi li applico. Penso ad esempio alla funzione memoize.
antirez writes: @Paolo: ciao Paolo... surprise, questo e' vero solo con i linguaggi scarsi come PHP & company ;) In quelli buoni c'e' un concetto che si chiama "tail recursion optimization" che elimina tale problema, dal punto di vista dello spazio il programma rimane asintoticamente identico a quello iterativo. Ne parlero' di certo in un prossimo articolo.
Paolo writes: Pero' tieni presente che scrivendo programmi in maniera' ricorsiva si puo' perdere molto in efficienza per mettere e togliere molti record nella stack ecc. :-) Molti programmatori ricorrono alla ricorsione solo quando non riescono a risolvere il problema in altro modo, e comunque anche in questo caso si puo' scrivere l'equivalente non ricorsivo di una funzione ricorsiva simulando la stack. Comunque si perde sempre in efficienza
antirez writes: Fra_T: anche in questo caso ci sei andato veramente vicino, dal punto di vista logico la soluzione e' completamente accettabile perche' il problema e' espresso e risolto in termini ricorsivi, l'imperfezione e' nella implementazione che usa invece merge + diff. Complimenti comunque :) Al prossimo post con le soluzioni.
Fra_T writes: Il massimo o cui sono arrivato per il terzo problema è questa funzione:
function sortlist($a) {
if(count($a) == 0) return array();
return array_merge(
(array) min($a),
sortlist(
array_diff(
$a, array( min($a) )
)
)
);
}
Solo che elimina dall'array ritornata i numero doppi... aspetterò le soluzioni :D
Fra_T writes: ah, grazie dell'info... ma veniamo alla prima :D Così?
function iseven($x){
if($x == 0) return true;
if($x == 1) return false;
return iseven($x-2);
}
antirez writes: @Fra_T: il secondo e' OK, il primo non e' ricorsivo :)
Un problema del secondo pero' e' che in realta' la echo dovrebbe essere estratta dalla ricorsione (basta mettere punto e virgola invece della virgola in pratica). C'e' un motivo preciso che si chiama tail recursion optimization per fare questo, e anche il fatto che in realta' il valore di ritorno non viene utilizzato.
Fra_T writes: Il 2° così può andare?
function printlist($a){
if($a)
echo $a[0], printlist(array_slice($a, 1));
}
Il primo lo farei così, ma non c'è ricorsione :D
function iseven($x){
if($x%2)
return false;
return true;
}
antirez writes: Ciao Fra_T: sei sulla buona strada con tutti e due i problemi ma in relata' le due soluzioni modificano delle variabili direttamente per cui si perde l'idea di descrizione del problema in termini di se stesso almeno in parte. Prova ad evitare array_shift e $x -= 2. Il secondo e' quasi perfetto dopo questa modifica mentre il primo (iseven) puo' essere semplificato in maniera massiccia.
Fra_T writes: Sono in difficoltà con il terzo problema :D
I primi due:
function iseven($x){
if($x == 0) return true;
if( ($x -= 2) <= 1 )
if($x) return false;
else return true;
return iseven($x);
}
function printlist($a){
if($a)
echo array_shift($a), printlist($a);
}
home