antirez weblog

Anche se non ci sono state molte risposte al post sui quesiti di programmazione spero ugualmente che qualcuno si sia cimentato a risolverli :) In ogni caso ecco le soluzioni ai quesiti proposti.

Soluzione al primo quesito

Come correttamente commentato da Gianni la soluzione al primo quesito e' ricorsiva, si tratta del seguente semplice programma:

function step_up() {
    if (!step()) {
        step_up();
        step_up();
    }
}

La funzione step_up non ritorna alcun valore perche' il suo funzionamento, al contrario della funzione step, e' garantito.

Perche' tale funzione esegue il compito di far salire l'automa un gradino, anche se in caso di fallimento della funzione step l'automa scende di un gradino, dovrebbe essere abbastanza chiaro:

• Se step ritorna true il programma non fa niente, il robot e' salito
• Se step ritorna false il programma deve far salire il robot di due posizioni per ritrovarsi un gradino piu' in alto rispetto alla posizione di partenza, dunque chiama due volte l'affidabile step_up.

Immaginate che la chiamata a step fallisca dentro la if. L'automa e' ora un gradino piu' sotto di dove dovrebbe essere, serve farlo salire due volte, per tale ragione chiamiamo ricorsivamente step_up due volte. La prima chiamata ricorsiva potrebbe chiamare step e vedere che questa fallisce, ma in tal caso ci saranno altre due chiamate ricorsive e cosi' via, la funzione continuera' a chiamarsi ricorsivamente fino a quando insomma tutte e due le chiamate a step_up non ritorneranno immediatamente con successo.

C'e' un modo per rendere il problema piu' chiaro riformulandolo. Facciamo finta che quando step ritorna true sale di un gradino, ma quando ritorna false semplicemente l'automa non si muove (invece di cadere di un gradino).

In tal caso la funzione step_up sarebbe:

function step_up() {
    if (!step())
        step_up();
}

Ora forse e' piu' chiaro. Se il robot e' incastrato step() continuera' a ritornare false, ma step_up continuera' con le chiamate ricorsive fino a quando una finalmente riesce a funzionare: a quel punto tutte le chiamate ricorsive ritorneranno, e la funzione avra' avuto successo.

In questo caso piu' semplice risulta estremamente evidente come la ricorsione in questo contesto sia stata utilizzata in maniera elegante per modellare un problema iterativo che sarebbe stato possibile esprimere con:

while (!step()) {
  /* niente da fare */
}

Qualcuno potrebbe pensare che questa soluzione e' molto piu' diretta: forse e' vero nel caso banale, nel caso piu' complesso dell'automa che cade quando la funzione fallisce la soluzione ricorsiva e' quasi ugualmente semplice! Mentre quella iterativa diventa molto piu' complessa e bisogna tenere un contatore di quanti gradini si e' scesi per recuperarli.

Soluzione al secondo quesito

Il semplicissimo programma la cui terminazione e' garantita ma che gira davvero molto a lungo e' un contatore che conta da 0 fino a (2^numbits)-1 e utilizza tutta la RAM del computer come un intero. numbits rappresenta insomma la quantita' di bit che possiede la memoria fisica del computer in questione, esclusi quelli occupati dal piccolo programma che implementa il contatore.

Con questo e tutto, ma in un post successivo cerchero' di approfondire un po' i concetti inerenti la ricorsione che sono stati sfiorati discutendo la soluzione al primo quesito.