La funzione ricorsiva in python
Nel linguaggio di programmazione python la ricorsione è una funzione che chiama se stessa.
def funzione():
...
funzione()
A cosa serve la ricorsione?
La funzione ricorsiva è utile per compiere delle operazioni ripetitive con poche righe di codice.
La ricorsione può avvenire una volta o più volte di seguito.
E' opportuno sottolineare che nello schema precedente la funzione A sta invocando se stessa ( funzione A ) durante la ricorsione e non un'altra funzione.
A questo punto il concetto di funzione ricorsiva dovrebbe essere abbastanza chiaro.
Nota. La ricorsione deve essere ben progettata altrimenti si rischia di incappare in un loop infinito di invocazioni. A un certo punto la funzione ricorsiva deve smettere di invocarsi.
Esempio di ricorsione in python
In questo script calcolo il fattoriale di un numero tramite una funzione ricorsiva.
- def fattoriale(n):
- if (n<2):
- return 1
- return n*fattoriale(n-1)
- y=fattoriale(5)
- print(y)
Nelle prime righe da 1 a 4 definisco la funzione ricorsiva fattoriale() tramite l'istruzione def.
La funzione fattoriale() accetta in input un solo argomento (n).
Nella riga 5 chiamo la funzione per la prima volta passandogli l'argomento n=3.
La funzione elabora il valore e alla riga 4 tenta di restituire il valore (n=3) moltiplicato per il risultato della funzione fattoriale(n-1) ossia fattoriale(2).
Quindi, la funzione richiama se stessa fornendo l'argomento 2 ( prima ricorsione ).
Il processo si ripete di nuovo durante la prima ricorsione.
La funzione cerca di restituire il prodotto tra il valore corrente (n=2) e il risultato della funzione fattoriale(n-1) ossia fattoriale(1).
Quindi richiama se stessa fornendo l'argomento 1 ( seconda ricorsione )
Nella ricorsione successiva la variabile n è uguale a 1.
Essendo inferiore a 2, l'istruzione if alla riga 3 termina la seconda ricorsione senza invocarsi di nuovo.
La funzione ricorsiva restituisce 1 alla funzione chiamante ( return 1 ).
Nota. In quest'ultimo caso la funzione non ha più chiamato se stessa. La ricorsione ha raggiunto il suo livello più profondo.
Il processo continua a ritroso fino alla prima ricorsione.
L'output finale del programma è il seguente:
6
Lo script ha calcolato il fattoriale 3! ossia 3·2·1=6.
E così via.
