Funzioni ricorsive

Cos’è la ricorsione?

Una funzione ricorsiva risolve un problema chiamando se stessa con una versione più piccola dello stesso problema.

Puoi pensare a una matrioska: apri una bambola, ne trovi una più piccola e ripeti finché arrivi a quella che non si apre più. Quella è il caso base.

Le due parti fondamentali

Ogni funzione ricorsiva deve avere:

1. Il caso base: la condizione che fa fermare la ricorsione
2. Il caso ricorsivo: dove la funzione chiama se stessa con un problema più piccolo

Senza il caso base, la funzione continuerebbe a chiamarsi e il programma terminerebbe con un errore.

Esempio classico: il fattoriale

Il fattoriale di un numero (scritto con il simbolo !) è il prodotto di tutti i numeri interi da 1 fino a quel numero:

5! = 5 × 4 × 3 × 2 × 1 = 120
3! = 3 × 2 × 1 = 6
1! = 1

Si può anche scrivere così: 5! = 5 × 4!. E 4! = 4 × 3!. A ogni passaggio il problema si riduce.

def fattoriale(n):
    # Caso base: se n è 0 o 1, il fattoriale è 1
    if n == 0 or n == 1:
        return 1
    # Caso ricorsivo: n * fattoriale del numero precedente
    return n * fattoriale(n - 1)

print(fattoriale(5))   # 120
print(fattoriale(3))   # 6

Questi sono i passaggi della chiamata fattoriale(5):

fattoriale(5)
  → 5 × fattoriale(4)
         → 4 × fattoriale(3)
                → 3 × fattoriale(2)
                       → 2 × fattoriale(1)
                              → 1  ← caso base, si ferma!

Quando raggiunge il caso base, Python risale calcolando 2×1=2, 3×2=6, 4×6=24 e 5×24=120.

Esempio: la successione di Fibonacci

La successione di Fibonacci è famosa in matematica e in natura: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Ogni numero è la somma dei due che lo precedono. Anche questo si presta alla ricorsione:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

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

Un limite importante

Python gestisce al massimo circa 1000 chiamate ricorsive annidate. Superato il limite, solleva un RecursionError. Per questo la ricorsione non è sempre adatta a problemi con numeri molto grandi.

Quando usare la ricorsione?

La ricorsione è utile quando il problema ha una struttura naturalmente “annidata”: un problema grande può essere descritto come una versione più piccola dello stesso problema.

Per problemi semplici (come contare fino a 100, o scorrere una lista), usa i cicli for o while: sono più veloci e più facili da capire.