Che cos’è la ricorsione?

La ricorsione è il processo di definizione di qualcosa in termini di se stesso.

Un esempio di mondo fisico sarebbe quello di posizionare due specchi paralleli uno di fronte all’altro. Qualsiasi oggetto tra di loro sarebbe riflesso ricorsivamente.

Python Funzione ricorsiva

In Python, sappiamo che una funzione può chiamare altre funzioni. È anche possibile che la funzione si chiami da sola. Questi tipi di costrutto sono definiti come funzioni ricorsive.

L’immagine seguente mostra il funzionamento di una funzione ricorsiva chiamatarecurse.

di Seguito è un esempio di una funzione ricorsiva per trovare il fattoriale di un numero intero.

Fattoriale di un numero è il prodotto di tutti gli interi da 1 a quel numero. Ad esempio, il fattoriale di 6 (indicato come 6!) è 1*2*3*4*5*6 = 720.

Esempio di 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 = 3print("The factorial of", num, "is", factorial(num))

Uscita

The factorial of 3 is 6

Nell’esempio precedente, factorial() è una funzione ricorsiva come si chiama.

Quando chiamiamo questa funzione con un numero intero positivo, si chiamerà ricorsivamente diminuendo il numero.

Ogni funzione moltiplica il numero con il fattoriale del numero sottostante fino a quando non è uguale a uno. Questa chiamata ricorsiva può essere spiegata nei passaggi seguenti.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

vediamo un immagine che mostra un passo-by-step processo di ciò che sta accadendo:

il Nostro ricorsione termina quando il numero si riduce a 1. Questo è chiamato la condizione di base.

Ogni funzione ricorsiva deve avere una condizione di base che interrompe la ricorsione altrimenti la funzione si chiama all’infinito.

L’interprete Python limita le profondità della ricorsione per evitare infinite ricorsioni, con conseguente overflow dello stack.

Per impostazione predefinita, la profondità massima di ricorsione è 1000. Se il limite viene superato, si ottieneRecursionError. Diamo un’occhiata a una di queste condizioni.

def recursor(): recursor()recursor()

Output

Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

I vantaggi della ricorsione

1. Le funzioni ricorsive rendono il codice pulito ed elegante.
2. Un compito complesso può essere suddiviso in sottoproblemi più semplici usando la ricorsione.
3. La generazione di sequenze è più semplice con la ricorsione rispetto all’utilizzo di un’iterazione nidificata.

Svantaggi della ricorsione

1. A volte la logica alla base della ricorsione è difficile da seguire.
2. Le chiamate ricorsive sono costose (inefficienti) in quanto occupano molta memoria e tempo.
3. Le funzioni ricorsive sono difficili da eseguire il debug.