In questo tutorial imparerai a creare una funzione ricorsiva (una funzione che chiama se stessa).
Cos'è la ricorsione?
La ricorsione è il processo di definizione di qualcosa in termini di se stessa.
Un esempio del mondo fisico potrebbe essere quello di posizionare due specchi paralleli uno di fronte all'altro. Qualsiasi oggetto tra di loro verrebbe riflesso in modo ricorsivo.
Funzione ricorsiva di Python
In Python, sappiamo che una funzione può chiamare altre funzioni. È anche possibile che la funzione chiami se stessa. Questi tipi di costrutti sono definiti funzioni ricorsive.
L'immagine seguente mostra il funzionamento di una funzione ricorsiva chiamata recurse.
Funzione ricorsiva in Python
Di seguito è riportato un esempio di una funzione ricorsiva per trovare il fattoriale di un numero intero.
Il fattoriale di un numero è il prodotto di tutti i numeri interi da 1 a quel numero. Ad esempio, il fattoriale di 6 (indicato come 6!) È 1 * 2 * 3 * 4 * 5 * 6 = 720.
Esempio di una funzione ricorsiva
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Produzione
Il fattoriale di 3 è 6
Nell'esempio sopra, factorial()è una funzione ricorsiva come si chiama.
Quando chiamiamo questa funzione con un numero intero positivo, si chiamerà ricorsivamente se stessa diminuendo il numero.
Ogni funzione moltiplica il numero per il fattoriale del numero sottostante fino a quando non è uguale a uno. Questa chiamata ricorsiva può essere spiegata nei passaggi seguenti.
fattoriale (3) # 1a chiamata con 3 3 * fattoriale (2) # 2a chiamata con 2 3 * 2 * fattoriale (1) # 3a chiamata con 1 3 * 2 * 1 # ritorno dalla 3a chiamata come numero = 1 3 * 2 # ritorno dalla 2a chiamata 6 # ritorno dalla 1a chiamata
Diamo un'occhiata a un'immagine che mostra un processo passo dopo passo di ciò che sta accadendo:
Lavoro di una funzione fattoriale ricorsiva
La nostra ricorsione termina quando il numero si riduce a 1. Questa è chiamata condizione di base.
Ogni funzione ricorsiva deve avere una condizione di base che arresti la ricorsione, altrimenti la funzione chiama se stessa all'infinito.
L'interprete Python limita la profondità della ricorsione per evitare ricorsioni infinite, con conseguente overflow dello stack.
Per impostazione predefinita, la profondità massima di ricorsione è 1000. Se il limite viene superato, si ottiene RecursionError. Diamo un'occhiata a una di queste condizioni.
def recursor(): recursor() recursor()
Produzione
Traceback (la chiamata più recente per ultima): File "", riga 3, in File "", riga 2, in un File "", riga 2, in un File "", riga 2, in a (Riga precedente ripetuta altre 996 volte ) RecursionError: profondità massima di ricorsione superata
Vantaggi della ricorsione
- Le funzioni ricorsive rendono il codice pulito ed elegante.
- Un'attività complessa può essere suddivisa in problemi secondari più semplici utilizzando la ricorsione.
- La generazione di sequenze è più facile con la ricorsione rispetto all'utilizzo di un'iterazione annidata.
Svantaggi della ricorsione
- A volte la logica alla base della ricorsione è difficile da seguire.
- Le chiamate ricorsive sono costose (inefficienti) in quanto occupano molta memoria e tempo.
- Le funzioni ricorsive sono difficili da eseguire il debug.
