Ricorsione (Recursion) in Python

In questo articolo, imparerai come creare funzioni ricorsive (funzioni che si chiamano da sole).

Cos'è la ricorsione in Python?

La ricorsione è il processo di definire qualcosa in termini di sé stesso.

Un esempio del mondo fisico è posizionare due specchi paralleli che si fronteggiano. Qualsiasi oggetto tra di loro viene riflettuto ricorsivamente.

Funzione ricorsiva Python

In Python, conosciamo unFunzionePuò chiamare altre funzioni. Le funzioni possono chiamarsi anche a loro volta. Questo tipo di costruzione si chiama funzione ricorsiva.

Ecco un esempio di funzione ricorsiva per trovare il factorial di un intero.

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

Esempio di funzione ricorsiva

def calc_factoriale(x):
　　　　"""
　　　　Funzione ricorsiva per calcolare il factorial di un intero
　　　　if x == 1:
　　　　　　　　return 1
　　　　else:
　　　　　　　　return (x * calc_factoriale(x-1))
num = 4
print("Il factorial di", num, "è", calc_factoriale(num))

Nell'esempio sopra, calc_factoriale() è una funzione ricorsiva che si chiama da sé.

Quando chiamiamo questa funzione con un numero naturale, essa si chiama ricorsivamente riducendo il numero.

Ogni funzione moltiplica un numero per il suo factorial inferiore fino a raggiungere 1. Questo richiamo ricorsivo può essere spiegato nei seguenti passaggi.

calc_factoriale(4) # 1a chiamata con 4
4 * calc_factoriale(3) # 2a chiamata con 3
4 * 3 * calc_factoriale(2) # 3a chiamata con 2
4 * 3 * 2 * calc_factorial(1)　　# 4th call with 1
4 * 3 * 2 * 1　　　　　　　　　　　　　　　　　　# return from 4th call as number=1
4 * 3 * 2　　　　　　　　　　　　　　　　　　　　　　# return from 3rd call
4 * 6　　　　　　　　　　　　　　　　　　　　　　　　　　# return from 2nd call
24　　　　　　　　　　　　　　　　　　　　　　　　　　　　　# return from 1st call

Quando il numero si riduce a 1, la ricorsione termina. Questo si chiama condizione di base.

Ogni funzione ricorsiva deve avere una condizione di base per fermare la ricorsione, altrimenti la funzione chiamerà se stessa in modo infinito.

L'interprete Python limita la profondità della ricorsione per aiutare a evitare la ricorsione infinita, che può causare un overflow dello stack.

Per impostazione predefinita, la profondità massima di ricorsione è 1000。Se superata la limitazione, il risultato è RecursionError. Vediamo un esempio di questa condizione.

def recursor():
　　　　recursor()
recursor()

Risultato di output

Traceback (chiamata più recente in basso):
　　File "<string>", riga 3, in <module>
　　File "<string>", riga 2, in a
　　File "<string>", riga 2, in a
　　File "<string>", riga 2, in a
　　[Riga precedente ripetuta 996 altre volte]
RecursionError: superata la profondità massima di ricorsione

I vantaggi della ricorsione

1. Le funzioni ricorsive rendono il codice pulito e ordinato.

2. Usare la ricorsione può decomporre compiti complessi in problemi più semplici.

3. Usare la ricorsione è più facile per generare sequenze rispetto all'uso di annidamenti.

I difetti della ricorsione

1. A volte, la logica dietro la ricorsione è difficile da seguire.

2. Le chiamate ricorsive sono costose (low efficiency) perché occupano una grande quantità di memoria e tempo.

3. Le funzioni ricorsive sono difficili da debuggare.