Ricorsione in Python

La ricorsione è una tecnica in cui una funzione chiama se stessa per risolvere un problema suddividendolo in sotto-problemi più piccoli e identici. Ogni chiamata lavora su una versione più semplice del problema originale fino a raggiungere un caso banale — il caso base — che può essere risolto direttamente.

Questo capitolo tratta:

• Come funziona la ricorsione e come appare il call stack
• Caso base e caso ricorsivo
• Problemi ricorsivi classici: fattoriale, Fibonacci, potenza, appiattimento
• Ricorsione vs iterazione — quando scegliere l'una o l'altra
• Il limite di ricorsione di Python e come aggirarlo
• Memoizzazione con functools.lru_cache

Come Funziona la Ricorsione

Quando una funzione chiama se stessa, Python aggiunge un nuovo stack frame al call stack per ogni chiamata. Ogni frame mantiene le proprie variabili locali. Quando viene raggiunto il caso base, i frame iniziano a restituire i valori in ordine inverso — ultimo entrato, primo uscito — finché la chiamata originale non riceve la risposta finale.

Una funzione ricorsiva valida ha sempre due parti:

Senza un caso base (o con uno che non viene mai raggiunto), la funzione chiama se stessa all'infinito e Python solleva un RecursionError.

Un Esempio Semplice: Conto alla Rovescia

La seguente funzione conta alla rovescia da n fino a zero e poi stampa "Go!". È facile da tracciare perché ogni chiamata riduce n di uno fino a quando n <= 0.

def countdown(n):
    if n <= 0:         # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)   # recursive case

countdown(5)

Output:

5
4
3
2
1
Go!

Traccia del call stack:

1. countdown(5) stampa 5, chiama countdown(4)
2. countdown(4) stampa 4, chiama countdown(3)
3. … e così via …
4. countdown(0) stampa "Go!" e ritorna — inizia lo svolgimento

Fattoriale

Il fattoriale di n (scritto n!) è il prodotto di tutti gli interi positivi fino a n. È definito ricorsivamente come:

• 0! = 1 (caso base)
• n! = n × (n − 1)! (caso ricorsivo)

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

factorial(5) si espande così prima che venga restituito qualsiasi valore:

factorial(5)
  5 * factorial(4)
        4 * factorial(3)
              3 * factorial(2)
                    2 * factorial(1)
                          1          ← base case

Poi le moltiplicazioni avvengono durante il ritorno: 1 → 2 → 6 → 24 → 120.

Sequenza di Fibonacci

La sequenza di Fibonacci è definita da: ogni numero è la somma dei due precedenti — 0, 1, 1, 2, 3, 5, 8, 13, …

def fibonacci(n):
    if n <= 0:   # base case
        return 0
    if n == 1:   # base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13

Questo è corretto ma lento per n grandi — fibonacci(40) esegue milioni di chiamate ridondanti. Vedi Memoizzazione di seguito per la soluzione.

Somma di una Lista

La ricorsione funziona in modo naturale sulle liste: si elabora il primo elemento, poi si ricorre sul resto.

def sum_list(lst):
    if not lst:              # base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))   # 15
print(sum_list([]))                 # 0

lst[1:] crea una nuova lista con il primo elemento rimosso, rendendo il problema più piccolo di un elemento ogni volta.

Elevare un Numero a una Potenza

def power(base, exp):
    if exp == 0:          # base case: anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 4))    # 81
print(power(5, 0))    # 1

Appiattimento di una Lista Annidata

Alcuni problemi sono intrinsecamente ricorsivi — hanno la stessa struttura a ogni livello. Appiattire una lista arbitrariamente annidata è uno di questi.

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse into sublists
        else:
            result.append(item)
    return result

print(flatten([1, [2, 3], [4, [5, 6]], 7]))
# [1, 2, 3, 4, 5, 6, 7]

Questo è difficile da scrivere in modo pulito con la sola iterazione perché la profondità di annidamento è sconosciuta.

Ricorsione vs Iterazione

La maggior parte degli algoritmi ricorsivi può essere riscritta come cicli iterativi, e viceversa.

Fattoriale iterativo

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))   # 120

Linea guida: scegli la ricorsione quando il problema si decompone naturalmente in sotto-problemi identici più piccoli e la profondità è modesta. Scegli l'iterazione quando hai bisogno di alte prestazioni o la profondità potrebbe essere elevata.

Il Limite di Ricorsione di Python

Python limita il call stack a 1 000 frame per impostazione predefinita per evitare che uno stack overflow faccia crashare il processo.

import sys
print(sys.getrecursionlimit())   # 1000

Se la tua funzione supera questo limite vedrai:

RecursionError: maximum recursion depth exceeded

Puoi aumentare il limite con sys.setrecursionlimit(n), ma fallo con cautela — uno stack molto profondo può esaurire la memoria di sistema. Per ricorsioni genuinamente profonde, riscrivi l'algoritmo iterativamente o usa i generator di Python per simulare uno stack manualmente.

Memoizzazione

La Fibonacci ricorsiva naïve è esponenzialmente lenta perché risolve gli stessi sotto-problemi più e più volte. La memoizzazione mette in cache il risultato di ogni chiamata unica in modo che venga calcolato una sola volta.

Cache manuale con un dizionario

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55
print(fibonacci(30))   # 832040

Uso di functools.lru_cache

La libreria standard fornisce un decoratore che gestisce la cache automaticamente:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))   # 55
print(fibonacci(50))   # 12586269025

@lru_cache trasforma un algoritmo altrimenti esponenziale in tempo lineare senza codice aggiuntivo nel corpo della funzione. È l'approccio Python idiomatico per memoizzare funzioni ricorsive pure.

Ricerca Binaria (Ricorsiva)

La ricerca binaria è un classico algoritmo divide-et-impera: si confronta il target con l'elemento centrale, poi si ricorre sulla metà sinistra o destra.

def binary_search(lst, target, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low > high:        # base case: search space exhausted
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search(lst, target, mid + 1, high)
    else:
        return binary_search(lst, target, low, mid - 1)

nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 1))    # 0
print(binary_search(nums, 15))   # 7
print(binary_search(nums, 4))    # -1  (not found)

Errori Comuni

Caso base mancante

# This will raise RecursionError
def broken(n):
    return n * broken(n - 1)   # no base case!

Chiediti sempre: "Qual è l'input più semplice che questa funzione deve gestire senza chiamare se stessa?"

Ricorsione infinita da un caso base errato

# factorial of a negative number loops forever
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # n goes -1, -2, -3 ...

# Fix: guard at the top
def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Argomento predefinito mutabile come memo

Usare memo={} come parametro predefinito è comodo ma condivide lo stato tra tutte le chiamate di livello superiore. Per il codice in produzione, passa la cache esplicitamente o usa @lru_cache.

Quando Usare la Ricorsione

La ricorsione è una scelta naturale per:

• Attraversamento di alberi e grafi — elenchi di directory, attraversamento del DOM, alberi decisionali
• Algoritmi divide-et-impera — merge sort, quicksort, ricerca binaria
• Definizioni matematiche — fattoriale, Fibonacci, combinatoria
• Backtracking — risoluzione di labirinti, Sudoku, generazione di permutazioni
• Strutture dati annidate — parsing di JSON/XML, appiattimento di liste annidate

Per semplici cicli sequenziali o grandi profondità, preferisci i cicli for o i cicli while.

Capitoli Correlati

• Funzioni Python — i mattoni su cui si basa la ricorsione
• Scope in Python — capire come funzionano le variabili locali in ogni frame
• Cicli While in Python — l'alternativa iterativa
• Generator Python — alternative efficienti in memoria per le sequenze
• Iteratori Python — il protocollo di iterazione alla base del modello di ciclo di Python
• Try Except in Python — gestire RecursionError in modo elegante

Esercizi