Pillole sulla Ricorsione

La ricorsione è una particolare tecnica di programmazione che consiste nel richiamare all'interno di una funzione, la funzione stessa, questa tecnica è particolarmente utile perchè si avvicina di più alla logica del pensiero umano e viene in aiuto con strutture complesse come gli Alberi, oppure il Quick Sort, il Quick Sort in particolare è di una difficoltà mostruosa da realizzare con algoritmi iterativi!

Ka ricorsione è inoltre importante, perchè gli algoritmi ricorsivi
generalmente possono essere testati e garantiti tramite il Principio di
Induzione Matematica. Questo significa che se si ha un problema e lo si  può risolvere ricorsivamente o iterativamente è sempre meglio risolverlo
ricorsivamente se si ha a cuore la sicurezza e l'affidabilità, perchè solo risolvendolo in questo modo si può dimostrare matematicamente che l'algoritmo è valido per tutti i valori di ingresso e tutti i possibili casi.

Che poi nella pratica si usano gli algoritmi iterativi a volte perchè quelli ricorsivi mandano in overflow lo stack, è un'altro discorso, è un discorso che non è molto valido ai giorni nostri siccome basta procurarsi macchine più potenti.

In conclusione comunque:

La ricorsione è ottima alleata della sicurezza e della funzionalità.

L'iteratività è ottima alleata della velocità e del risparmio di risorse.

Sta poi di volta in volta decidere quale è preferibile.

Ci sono casi in cui per esempio come nel caso della potenza, che è indifferente, scegliere l'uno o l'altro metodo, ma in altri come per esempio il Quick Sort, è preferibile optare per algoritmi ricorsivi.

Infassi se si scrivesse il Quick Sort, iterativamente (ammesso che ci si riesca) non si potrebbe mai dimostrare che funziona per tutti gli insiemi di ingresso, mentre il QuickSort Ricorsivo si può dimostrare sfruttando il Principio di Induzione Matematica.



Giovanni Ceglia
giovanniceglia@xungame.com