Ricorsione

Definizione

Definizione (funzione ricorsiva). Una funzione è ricorsiva se chiama se stessa. Si scrive come una dimostrazione per induzione:

• caso base: input abbastanza piccolo da risolvere direttamente;
• passo ricorsivo: si riduce il problema a uno (o più) problemi dello stesso tipo più piccoli e si combina il risultato.

def fattoriale(n):
    """n! per n >= 0."""
    if n == 0:                 # caso base
        return 1
    return n * fattoriale(n - 1)   # passo: problema di taglia n-1

Per essere corretta: ogni chiamata deve avvicinarsi al caso base e il caso base deve essere sempre raggiunto.

Esempio. fattoriale(4) restituisce 24 e si ferma sul caso base fattoriale(0) == 1.

Stack delle chiamate

Ogni chiamata crea un record di attivazione (frame) sullo stack con parametri, variabili locali e punto di ritorno. Le chiamate ricorsive impilano frame distinti: ogni n è una variabile diversa.

fattoriale(3)
  3 * fattoriale(2)
        2 * fattoriale(1)
              1 * fattoriale(0)
                    -> 1
              -> 1
        -> 2
  -> 6

Proprietà (limite della profondità di ricorsione). Lo stack ha dimensione limitata: in Python il limite predefinito è circa 1000 chiamate annidate (sys.getrecursionlimit()), oltre si ottiene RecursionError. Senza caso base (o con un caso base mai raggiunto, es. fattoriale(-1)) la ricorsione è infinita. In C lo stack esaurito provoca un stack overflow (vedi Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).

Esempio. In Python sys.getrecursionlimit() restituisce 1000: una funzione senza caso base solleva RecursionError.

Esempi

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

def potenza(b, e):
    """b**e con O(log e) moltiplicazioni (e >= 0)."""
    if e == 0:
        return 1
    meta = potenza(b, e // 2)
    return meta * meta if e % 2 == 0 else meta * meta * b

def palindroma(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and palindroma(s[1:-1])

def somma_lista(v, i=0):
    """Somma di v[i:], senza creare copie della lista."""
    if i == len(v):
        return 0
    return v[i] + somma_lista(v, i + 1)

Nota: s[1:-1] crea una nuova stringa a ogni chiamata (costo lineare); passare indici, come in somma_lista, evita le copie.

Ricorsione multipla

Proprietà (ricorsione multipla: chiamate di fib)

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

L'albero delle chiamate ricalcola gli stessi valori moltissime volte: il numero di chiamate cresce come $\varphi^n$ con $\varphi \approx 1{,}618$ (esponenziale). Rimedi: versione iterativa, oppure memoizzazione (salvare i risultati già calcolati):

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)   # ora O(n) chiamate

Esempio. fib(5) esegue 15 chiamate; con @cache ogni valore è calcolato una volta sola.

Divide et impera

Definizione (divide et impera). Schema: dividere il problema in sottoproblemi indipendenti, risolverli ricorsivamente, combinare. Esempi: ricerca binariaRicerca lineare su sequenze qualsiasi in O(n); ricerca binaria su sequenze ordinate in O(log n), versione iterativa e ricorsiva, invariante e errori di indice; modulo bisect.Ricerca lineare e binaria → (un sottoproblema di metà taglia) e merge sort (due sottoproblemi di metà taglia, vedi Algoritmi di ordinamentoSelection sort, insertion sort e bubble sort (quadratici), merge sort (n log n, divide et impera); stabilità, ordinamento sul posto, costo nei vari casi; sort e sorted con key.Algoritmi di ordinamento →).

def massimo(v, lo, hi):
    """Massimo di v[lo:hi], hi > lo."""
    if hi - lo == 1:
        return v[lo]
    m = (lo + hi) // 2
    return max(massimo(v, lo, m), massimo(v, m, hi))

Esempio. massimo([3, 8, 2, 9, 4], 0, 5) restituisce 9, dividendo l'intervallo [0, 5) in [0, 2) e [2, 5).

Ricorsione o iterazione?

Ogni funzione ricorsiva si può riscrivere con un ciclo (eventualmente con uno stack esplicito, vedi Pila e codaPila (LIFO) e coda (FIFO) come ADT: operazioni e costi; realizzazione in Python con list e collections.deque; realizzazione in C con array e indici, coda circolare; applicazioni (parentesi bilanciate, stack delle chiamate, visite).Pila e coda →) e viceversa.

• Ricorsione: naturale per strutture ricorsive (alberi, liste concatenate, frattali) e per divide et impera; codice più vicino alla definizione matematica.
• Iterazione: niente costo dei frame né limite di profondità; preferibile per ricorsioni "lineari" lunghe (fattoriale, somma di una lista).

Errori tipici

• Caso base mancante o non raggiungibile (es. n == 0 quando n scende di 2 partendo da un dispari).
• Dimenticare il return davanti alla chiamata ricorsiva: il risultato viene calcolato e buttato, la funzione restituisce None.
• Ricorsione multipla senza memoizzazione su input grandi.