La ricorsione

Una funzione ricorsiva è una funzione che chiama se stessa. Serve per i problemi che si possono spezzare in una versione più piccola dello stesso problema.

Il fattoriale

Il fattoriale di un numero n (si scrive n!) è il prodotto di tutti i numeri da 1 a n: 5! = 5 × 4 × 3 × 2 × 1 = 120. Ma si può anche dire che 5! = 5 × 4!, e che 4! = 4 × 3!, e così via fino a 0! = 1.

def fattoriale(n):
    if n == 0:                       # caso base: si ferma
        return 1
    return n * fattoriale(n - 1)     # caso ricorsivo: un problema più piccolo

print(fattoriale(5))   # 120

Ogni funzione ricorsiva ha due parti:

• il caso base, che dà la risposta direttamente e ferma la ricorsione
• il caso ricorsivo, in cui la funzione richiama se stessa con un input più piccolo

Attenzione: senza caso base la funzione si richiama all'infinito e Python si ferma con RecursionError.

Come procede il calcolo

fattoriale(3)
= 3 * fattoriale(2)
= 3 * 2 * fattoriale(1)
= 3 * 2 * 1 * fattoriale(0)
= 3 * 2 * 1 * 1
= 6

Ricorsione su stringhe e liste

Lo stesso schema funziona con qualunque cosa si possa accorciare:

def inverti(s):
    if len(s) <= 1:
        return s
    return inverti(s[1:]) + s[0]

def somma_lista(lista):
    if not lista:              # lista vuota
        return 0
    return lista[0] + somma_lista(lista[1:])

print(inverti("python"))           # nohtyp
print(somma_lista([4, 8, 15, 16])) # 43

Quando la ricorsione è lenta: Fibonacci

Nella successione di Fibonacci ogni numero è la somma dei due precedenti: 0, 1, 1, 2, 3, 5, 8, 13…

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))   # 55

È elegante ma lentissima: per calcolare fib(35) la funzione ricalcola gli stessi valori milioni di volte. Provalo e cronometra.

I decoratori e @lru_cache

Un decoratore è una funzione che modifica il comportamento di un'altra funzione senza toccarne il codice. Si scrive con @ sopra la definizione.

Python ne ha uno pronto, @lru_cache, che ricorda i risultati già calcolati: se la funzione viene richiamata con lo stesso argomento, restituisce subito il valore salvato.

from functools import lru_cache

@lru_cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))   # istantaneo

Un decoratore fatto da te

def annuncia(funzione):
    def nuova(*args):
        print(f"Sto chiamando {funzione.__name__}{args}")
        return funzione(*args)
    return nuova

@annuncia
def somma(a, b):
    return a + b

print(somma(2, 3))

Esercizi

def potenza(base, esponente):
    if esponente == 0:
        return 1
    return base * potenza(base, esponente - 1)

print(potenza(2, 10))   # 1024

def somma_cifre(n):
    if n < 10:
        return n
    return n % 10 + somma_cifre(n // 10)

print(somma_cifre(1234))   # 10

def palindromo(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return palindromo(s[1:-1])

print(palindromo("radar"))   # True
print(palindromo("python"))  # False

def cerca(lista, valore):
    if not lista:
        return False
    centro = len(lista) // 2
    if lista[centro] == valore:
        return True
    if valore < lista[centro]:
        return cerca(lista[:centro], valore)
    return cerca(lista[centro + 1:], valore)

numeri = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(cerca(numeri, 23))   # True
print(cerca(numeri, 7))    # False