La ricorsione

Siamo finalmente giunti alla ricorsione. Croce e delizia del popolo dei programmatori. Per alcuni di voi sarà uno strumento utilissimo di cui non potrete fare a meno, per gli altri sarà l'incubo che li sveglierà durante la notte.

Cominciamo col dare una definizione. Cosa si intende in generale per ricorsione?
Per ricorsione si intende quel meccanismo tramite il quale un qualcosa, in genere funzioni o entità matematiche, è espresso in termini di sé stessa.

Quindi un concetto ricorsivo è qualcosa che è definito su se stesso.

Lo sono molte funzioni matematiche, algoritmi e strutture di dati. Per fare solo alcuni degli esempi più famosi basta citare l'MCM, il fattoriale, gli alberi e le grammatiche.

Alcuni potrebbero obbiettare che in fondo algoritmi come il fattoriale sono intuitivi e semplici da realizzare anche con un ciclo. Perché dovremmo perdere la testa con queste amenità? Il fatto è che non tutti gli algoritmi sono come quelli appena citati.
Ne esistono alcuni che se scritti tramite la ricorsione risultano incredibilmente più veloci e il codice da scrivere è molto inferiore ad una implementazione iterativa.

Il problema è che non tutti riescono a pensare ad un algoritmo in modo ricorsivo e questo porta a molti errori e ai loop.
I loop sono il più grande pericolo di chi scrive funzioni ricorsive. Si dice infatti che una funzione, quando entra in loop, non riesce ad uscire dal ciclo e non termina mai bloccando di fatto il programma.

In genere è possibile suddividere una funzione ricorsiva in tre grandi blocchi: l'invariante, la terminazione e la progressione.
L'invariante è quella condizione che indica quando si deve procedere con l'esecuzione della sequenza di funzioni ricorsive.
La terminazione specifica che output deve dare la funzione quando non è valida la condizione dell'invariante.
Ed in fine la progressione che descrive in che modo ottenere la nuova azione a partire dalla precedente.

Una volta trovati questi tre macroblocchi è facile comporli per ottenere una funzione ricorsiva funzionante.

<?php
 
/*
 esempio di una funzione ricorsiva che calcola l'mcm di due numeri
 in questo caso:
 Invariante: $a > $b
 Terminazione: $a == $b allora $a
 Progressione: Se $a > $b allora $a - $b, $b altrimenti $a, $b - $a
*/
 
function mcm ($a , $b)
{
  return (($a == $b) ? $a :
                (($a > $b) ? mcm($a - $b, $b) : mcm($a, $b - $a)));
}
 
?>

Ho volutamente usato un algoritmo semplice per spiegare. In questo modo spero di non aver spaventato nessuno. Per ora non andrò avanti con la ricorsione ma consiglio a tutti di cercare su internet documenti di approfondimento e a fare esercizi che vi aiuteranno di sicuro.

Inserisci un commento:


Il contenuto di questo campo è tenuto riservato e non verrà reso pubblico.

Condividi
Del.icio.us Digg Furl Google Ask
Yahoo! Segnalo Technorati Windows Live Facebook
Smarking Slashdot Taggly Ma.gnolia co.mments

Se ti piace questo articolo, puoi collegarlo al tuo sito copiando il seguente codice HTML nelle tue pagine.

Acquista libri di informatica

Acquista qui il tuo software

Ultimi commenti