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.

come funziona la ricorsione in python

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.

    1. def fattoriale(n):
    2. if (n<2):
    3. return 1
    4. return n*fattoriale(n-1)
    5. y=fattoriale(5)
    6. 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 prima chiamata della funzione

    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 ).

    la 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 )

    la 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 ).

    la ricorsione termina

    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.

    alla fine della ricorsione la funzione restituisce i valori elaborato alla funzione che l'ha chiamata

    L'output finale del programma è il seguente:

    6

    Lo script ha calcolato il fattoriale 3! ossia 3·2·1=6.

    E così via.

     


     

    Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

    FacebookTwitterLinkedinLinkedin
    knowledge base

    Le funzioni in python