Ricorsione in Python: concetti, esempi e consigli

La ricorsione è un concetto fondamentale nella programmazione e ha un'importanza particolare in Python. Indica la tecnica con cui una funzione richiama se stessa per risolvere un problema, scomponendolo in sottoproblemi più piccoli e gestibili. 

Questo metodo permette soluzioni eleganti e concise, soprattutto quando si affrontano problemi che implicano compiti ripetitivi o strutture gerarchiche. In Python, la ricorsione è usata in una varietà di applicazioni, dagli algoritmi di ordinamento all'esplorazione di dati complessi. 

Le soluzioni ricorsive spesso rispecchiano le definizioni matematiche dei problemi, risultando intuitive per chi ha familiarità con il ragionamento matematico. Il bello della ricorsione sta nella capacità di esprimere algoritmi complessi in poche righe di codice, creando soluzioni eleganti e leggibili. Tuttavia, padroneggiarla richiede un cambio di prospettiva rispetto agli approcci iterativi più comuni.

In questo articolo esplorerò il concetto di ricorsione, come funziona in Python e le sue applicazioni pratiche, includendo una discussione sui problemi più comuni e un confronto con l'iterazione. Se sei alle prime armi con Python, valuta di seguire uno dei nostri corsi, come Introduzione a Python, Concetti di paradigma di programmazione o Fondamenti di programmazione in Python.

Cos'è la ricorsione in Python?

In Python, la ricorsione indica una funzione che richiama se stessa per risolvere un problema. Comporta due componenti fondamentali:

• Caso base: è la condizione che termina la ricorsione. Senza di essa, le chiamate ricorsive continuerebbero all'infinito, causando alla fine il crash della funzione o l'esaurimento della memoria disponibile.
• Caso ricorsivo: questa parte della funzione scompone il problema in parti più piccole e richiama la funzione con tali parti ridotte.

Ecco un modo semplice per pensare alla ricorsione: immagina una funzione che risolve un problema complesso risolvendo versioni più piccole dello stesso problema, fino a raggiungere una soluzione che non richiede ulteriore ricorsione.

L'approccio ricorsivo segue la strategia "divide et impera", scomponendo i problemi complessi in versioni più semplici fino a raggiungere un caso banale. Spesso questo approccio rispecchia il nostro modo naturale di ragionare. Ad esempio, quando ordiniamo un mazzo di carte, potremmo ordinare gruppi più piccoli e poi combinarli, che è essenzialmente il modo in cui funzionano gli algoritmi di ordinamento ricorsivi come merge sort.

Ogni funzione ricorsiva deve avere almeno un caso base e almeno un caso ricorsivo. Il caso base impedisce la ricorsione infinita fornendo una condizione che non richiede ulteriori chiamate. Il caso ricorsivo riduce la dimensione del problema a ogni chiamata, garantendo che il caso base venga raggiunto.

Come funziona la ricorsione in Python?

La ricorsione funziona permettendo a una funzione di richiamare se stessa con argomenti modificati, risolvendo gradualmente il problema a passi più piccoli. Per capirlo in modo più concreto, considera il compito di calcolare la somma dei numeri da 1 a num.

Ecco un semplice approccio ricorsivo per calcolare la somma:

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 

6

In questa funzione, il caso base è quando num == 1, che ferma la ricorsione. Altrimenti, la funzione richiama se stessa con num - 1 fino a raggiungere il caso base.

Come funziona passo dopo passo:

1. sum_recursive(3) richiama sum_recursive(2).
2. sum_recursive(2) richiama sum_recursive(1).
3. sum_recursive(1) restituisce 1 (caso base).
4. Ora, sum_recursive(2) può restituire 2 + 1 = 3 e sum_recursive(3) può restituire 3 + 3 = 6.

Un altro esempio è una funzione ricorsiva per calcolare la potenza di un numero:

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))

8

Spiegazione passo passo di questa funzione power:

• power(2, 3) richiama power(2, 2).
• power(2, 2) richiama power(2, 1).
• power(2, 1) richiama power(2, 0).
• power(2, 0) restituisce 1 (caso base).
• Ora, tornando indietro: power(2, 1) restituisce 2 * 1 = 2.
• Poi power(2, 2) restituisce 2 * 2 = 4.
• Infine, power(2, 3) restituisce 2 * 4 = 8.

Quando una funzione ricorsiva viene chiamata, ogni chiamata crea una nuova voce nello stack delle chiamate. Questo stack tiene traccia di tutte le chiamate di funzione e delle loro variabili. Quando si raggiunge il caso base, lo stack inizia a risolvere ogni chiamata in ordine inverso, calcolando il risultato finale passo dopo passo.

Capire questo comportamento dello stack è fondamentale perché spiega sia la potenza sia i limiti della ricorsione in Python. Conserva elegantemente il contesto, ma può anche portare a problemi di memoria con ricorsioni profonde.

Implementare il fattoriale in Python usando la ricorsione

La funzione fattoriale è un classico esempio usato per dimostrare la ricorsione. Il fattoriale di un numero n, indicato con n!, è il prodotto di tutti gli interi positivi minori o uguali a n. Matematicamente:

n! = n × (n − 1) × (n − 2) × … × 1

Ricorsivamente, la funzione fattoriale può essere definita come:

n! = n × (n − 1)!

Implementiamolo in Python:

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1

24

Spiegazione passo passo del codice:

• La funzione compute_factorial(num) controlla se num == 0 e in tal caso restituisce 1.
• Altrimenti, restituisce num * compute_factorial(num - 1), dove la funzione richiama se stessa con un valore di num più piccolo.

La funzione fattoriale illustra perfettamente l'eleganza della ricorsione. La definizione matematica stessa è ricorsiva, rendendo l'implementazione del codice intuitiva e ben allineata al concetto matematico. Questa è una delle forze della ricorsione: permette al codice di esprimere direttamente definizioni matematiche.

Vale la pena notare che ci sono casi limite da considerare. Ad esempio, il fattoriale è in genere definito solo per interi non negativi. Un'implementazione robusta potrebbe includere la gestione degli errori per input negativi o controlli di tipo. 

Inoltre, per valori grandi di num, la soluzione ricorsiva può portare a uno stack overflow, una limitazione di cui parlerò più in dettaglio.

Problemi comuni: come correggere gli errori di ricorsione in Python

Sebbene la ricorsione sia uno strumento potente, è soggetta ad alcuni problemi comuni, come:

Superare la profondità massima di ricorsione

Python ha un limite di ricorsione predefinito di 1000 chiamate. Se una funzione ricorsiva si richiama troppe volte, verrà generato un RecursionError.

Ecco come risolvere:

Puoi aumentare la profondità di ricorsione usando sys.setrecursionlimit(). Tuttavia, non è consigliato se non strettamente necessario, perché può causare uno stack overflow.

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  

Current limit: 1000
Current limit after change: 200

Mancanza del caso base

Un caso base mancante o errato farà sì che la funzione ricorra all'infinito, portando a uno stack overflow.

Per risolvere, assicurati che il tuo caso base sia ben definito e raggiungibile.

Come interrompere la ricorsione in Python

La chiave per interrompere la ricorsione in Python è definire un corretto caso base. Senza di esso, la ricorsione non terminerà mai e genererà un errore.

Per esempio, nella funzione fattoriale che ho implementato prima, il caso base era if num == 0, che ferma la ricorsione. In generale, devi assicurarti che ogni funzione ricorsiva abbia una condizione in cui termina.

Progettare casi base efficaci richiede attenzione. Alcune linee guida includono:

• Identificare la versione più semplice del problema che può essere risolta direttamente.
• Garantire che tutti i percorsi ricorsivi raggiungano infine un caso base.
• Testare separatamente i casi limite per verificare che siano gestiti correttamente.
• Considerare più casi base se il problema lo richiede.

A volte sono utili tecniche di programmazione difensiva, aggiungendo controlli per input non validi o verifiche a runtime per prevenire profondità di ricorsione eccessive. Ad esempio:

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) 

120

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) 

ValueError: Maximum recursion depth exceeded

Questo approccio ti permette di impostare limiti personalizzati e fornire messaggi di errore più significativi rispetto al RecursionError predefinito.

Ecco un altro esempio che mostra un modo diverso di definire i casi base: trovare il massimo comun divisore (MCD) di due numeri usando la ricorsione.

Il MCD di due numeri x e y può essere calcolato con l'algoritmo di Euclide, usando l' operatore modulo %:

• Caso base: se y == 0, il MCD è x.
• Caso ricorsivo: altrimenti, il MCD di x e y è lo stesso del MCD di y e x % y.

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  

6

Ricorsione vs. iterazione in Python

Sia la ricorsione che l'iterazione possono risolvere molti degli stessi problemi, ma ciascuna ha pro e contro:

• La ricorsione è spesso più elegante e facile da capire, specialmente per problemi con una struttura naturalmente ricorsiva (ad es. attraversamenti di alberi, fattoriali, numeri di Fibonacci).
• L'iterazione può essere più efficiente perché non comporta l'overhead di molte chiamate di funzione ed evita problemi di stack overflow. Le soluzioni iterative di solito sono più parchi di memoria.

Quando usare la ricorsione:

• Quando il problema può essere naturalmente diviso in sottoproblemi più piccoli.
• Per problemi che coinvolgono strutture dati gerarchiche, come gli alberi.
• Quando la soluzione in forma ricorsiva è più intuitiva e porta a codice più pulito.
• Quando la leggibilità del codice è prioritaria rispetto all'ottimizzazione delle prestazioni.
• Quando lavori con dati di profondità sconosciuta (come l'analisi di JSON o XML annidati).

Quando usare l'iterazione:

• Per problemi che richiedono compiti ripetitivi senza scomporre il problema in sottoproblemi più piccoli.
• Per attività critiche in termini di prestazioni, dove una ricorsione profonda potrebbe comportare un uso elevato di memoria.
• Quando lavori con dataset di grandi dimensioni che potrebbero superare il limite di ricorsione.
• Quando l'uso della memoria è una preoccupazione primaria.
• Per problemi che sono naturalmente sequenziali piuttosto che gerarchici.

Confrontiamo implementazioni ricorsive e iterative dello stesso problema, calcolare la somma dei numeri da 1 a num:

Ricorsiva:

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)

Iterativa:

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return total

La versione iterativa usa un ciclo per accumulare la somma, mentre la versione ricorsiva scompone il problema nell'aggiungere n alla somma dei numeri da 1 a num - 1. Sebbene entrambe le soluzioni funzionino, la versione iterativa sarà più efficiente per valori grandi di num, perché non comporta l'overhead di più chiamate di funzione.

Alcuni problemi naturalmente ricorsivi possono essere trasformati in soluzioni iterative usando uno stack o una coda per simulare le chiamate ricorsive. Questa tecnica è particolarmente utile quando si lavora con attraversamenti di alberi o grafi.

Esempi pratici di ricorsione in Python

La ricorsione può essere applicata a vari problemi interessanti:

1. Calcolo dei numeri di Fibonacci

La sequenza di Fibonacci è definita ricorsivamente come:

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

Questo produce la seguente sequenza:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Ecco come potresti implementarla:

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))

8

Tuttavia, questa implementazione ingenua ricalcola più volte gli stessi valori. Un approccio più efficiente usa la memoization, che memorizza i risultati già calcolati (caching) per evitare calcoli ridondanti, riducendo significativamente i tempi di computazione:

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]

Questo può essere ulteriormente semplificato usando il decoratore lru_cache() dal modulo functools:

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)

2. Attraversare strutture dati annidate

La ricorsione è utile anche per lavorare con strutture dati annidate come liste di liste o oggetti JSON. Ad esempio, attraversare una struttura di directory o appiattire ricorsivamente una lista annidata.

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

nested_structure = [1, [2, 3], [4, [5, 6]]]

print(flatten(nested_structure))  

[1, 2, 3, 4, 5, 6]

3. Algoritmi di ordinamento (ad es., quick sort o merge sort) 

Algoritmi di ordinamento come quick sort e merge sort si basano fortemente sulla ricorsione. In questi algoritmi, il problema è scomposto in sottoproblemi più piccoli, che vengono ordinati ricorsivamente.

Ecco una semplice implementazione di quicksort:

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))

[16, 33, 150, 220, 400]

Conclusione

La ricorsione è un concetto potente in Python che aiuta a risolvere problemi complessi scomponendoli in sottoproblemi più semplici. Se usata correttamente, porta a codice pulito, conciso e facile da comprendere. 

Tuttavia, è essenziale definire corretti casi base e tenere presente la profondità di ricorsione per evitare gli errori più comuni. 

Sebbene a volte la ricorsione possa essere meno efficiente dell'iterazione, è uno strumento prezioso per risolvere determinati tipi di problemi, in particolare quelli che coinvolgono dati gerarchici o che si prestano naturalmente a soluzioni ricorsive.

Comprendendo la ricorsione e facendo pratica con esempi come fattoriali, sequenze di Fibonacci e algoritmi di ordinamento, sarai ben attrezzato per sfruttarla nei tuoi progetti Python.

Se ti interessano argomenti Python più avanzati in cui poter implementare la ricorsione, dai un'occhiata ai seguenti percorsi di apprendimento: Python Programming, Data Analyst in Python e Associate Data Scientist in Python