Follow

Per capire la ricorsione bisogna innanzitutto capire la ricorsione...

Ora conosciamo sufficientemente la struttura della memoria e i principi del suo funzionamento. Per spiegare lo stack, in particolare, ho dovuto fare richiamo alle funzioni.

Le funzioni sono un argomento fondamentale della programmazione e alcuni processori le implementano addirittura a livello di assembly.

Il concetto di funzione è molto semplice. Una funzione può essere vista come una “macchina” che riceve in pasto dei dati, li elabora e a volte restituisce un risultato.

La funzione “+” è una funzione che prende come dati due numeri (parametri), gli somma (corpo della funzione) e restituisce il risultato (valore di ritorno). La funzione print (presente in molti linguaggi) prende come dati una stringa e gli elabora stampandoli sullo schermo.

Le funzioni sono definibili dall’utente e tutti i linguaggi permettono di definire funzioni.

Ma come funziona una funzione ( 😀 )?

Con lo stack. Quando chiamiamo una funzione il computer crea un nuovo elemento in cima allo stack chiamato record di attivazione che contiene la copia dei dati passati per parametro, il puntatore all’ultima istruzione eseguita nella funzione “madre” e lo spazio per il valore di ritorno.

Quasi tutte le funzioni tradizionali sono funzioni iterative ovvero che ricavano la loro soluzione solo mediante i dati e altre funzioni.

Questo meccanismo dello stack però permette di implementare un altro strumento molto potente: la ricorsione.

La ricorsione consiste nell’usare una funzione (con parametri più piccoli) all’interno della stessa funzione. Consiste cioè nel risolvere un problema risolvendone uno di taglia minore.

Per esempio potremo pensare ad una versione ricorsiva della moltiplicazione:

def moltiplicazione(x,y) :
    if y == 1 : return x
    return x + moltiplicazione(y-1) :

Come si vede si risolve x*y risolvendo x*(y-1) + x … e cosi via.

Dall’esempio vediamo che una funzione ricorsiva si divide in:

• Uno o più CASI BASE: ovvero le condizioni immediate, la cui soluzione non necessita di usare la ricorsione. (nell’esempio è il caso x*1 = x)
• Uno o più CASI RICORSIVI: ovvero i casi in cui si usa la ricorsione.

Ovviamente i casi base sono necessari per far terminare la ricorsione. (Una ricorsione infinita causa uno stack overflow ovvero lo stack si mangia tutta la memoria a disposizione).

Le soluzioni ricorsive sono molto eleganti ma hanno lo svantaggio che la pila dei record di attivazione e la loro creazione “mangia” risorse non necessarie esclusivamente alla risoluzione del problema. Quindi nei casi di programmi che necessitano di alte prestazioni tutti gli algoritmi ricorsivi vengono convertiti in iterativi.

Ma è sempre possibile?

Si. Dato un algoritmo ricorsivo è SEMPRE possibile scrivere il suo corrispettivo iterativo.

Il caso più semplice è quello in cui la ricorsione è l’ultima operazione della funzione. Questi casi vengono chiamati tail recursion e molti compilatori sono in grado di individuarli e convertirli in automatico nella loro versione iterativa.

Casi più complessi invece vengono convertiti usando una pila artificiale creata dal programmatore che essendo fatta ad-hoc per l’algoritmo contiene solo le informazioni necessarie e quindi è molto più efficente!