Lezioni Python: Le procedure ricorsive in Python

Una procedura ricorsiva rappresenta una costruzione artificiosa che ci consente di utilizzare una funzione in se stessa. Vediamo allora come è possibile utilizzare una tale funzione in ambiente Python; per farlo analizzeremo dapprima un semplice esempio di funzione ricorsiva alfine di mettere in evidenza appunto il fatto che la funzione richiama se stessa:

def factorial( n ):
   if n <1:   # per valori minori di 1 ritorna 1
       return 1
   else:
       return n * factorial( n - 1 )  # chiamata alla funzione ricorsiva

Analizziamo allora nel dettaglio la funzione che presenta una struttura ramificata. La condizione n == 0 è la base della ricorsione. Questo è l’unico modo che si ha per ottenere che il programma smetta di chiamare se stesso.

Le procedure ricorsive in Python

La parte contenuta nel costrutto else rappresenta la ricorsione. C'è da notare che la chiamata factorial(n-1) avviene all'interno della funzione che sta definendo factorial(n). La parte essenziale di tutto il procedimento di ricorsione è appunto la chiamata a un valore inferiore, n-1, e tale chiamata continuerà fino a quando non si verificherà un valore di n pari a 0.

Possiamo quindi affermare che una procedura di ricorsione che abbia successo chiamerà sempre un valore inferiore.Ci sono molti pericoli connessi all'utilizzo di un algoritmo di ricorsione. Ad esempio così come accade con i cicli while, è possibile per la funzione di chiamare se stessa all'infinito in modo da non fornire mai una risposta. Un'altro problema che può nascere dal suo utilizzo è legato al fatto che la ricorsione può causare calcoli ridondanti che, anche se possono essere conclusi, possono richiedere molto tempo. Infine mentre un programma ricorsivo è in esecuzione ha bisogno di spazio in più per accogliere l’overhead della ricorsione.

PER APPROFONDIRE L’ARGOMENTO CLICCARE SUL LINK SEGUENTE: