Funzioni Ricorsive in Python

Codegrind Team•Sep 11 2024

Le funzioni ricorsive sono funzioni che si richiamano all’interno della loro definizione. La ricorsione è una potente tecnica che permette di risolvere problemi complessi suddividendoli in sotto-problemi più semplici. In questo articolo vedremo come funzionano le funzioni ricorsive in Python, quando utilizzarle e come evitare problemi comuni come la ricorsione infinita.

Cos’è una Funzione Ricorsiva?

Una funzione ricorsiva è una funzione che richiama se stessa all’interno del proprio corpo. Quando si utilizza la ricorsione, è fondamentale avere una condizione di uscita (o caso base) per evitare di entrare in un ciclo infinito di chiamate ricorsive.

Struttura di una Funzione Ricorsiva

Una funzione ricorsiva segue solitamente questa struttura:

Caso base: La condizione che termina la ricorsione.
Chiamata ricorsiva: La funzione richiama se stessa con un input modificato, avvicinandosi al caso base.

Ecco un esempio di una funzione ricorsiva semplice che conta da 1 a un numero dato:

def conta(n):
    if n <= 0:  # Caso base
        return
    else:
        conta(n - 1)  # Chiamata ricorsiva
        print(n)

conta(5)

Output:

In questo esempio:

La funzione conta richiama se stessa con un valore ridotto (n - 1), avvicinandosi al caso base (n <= 0).
Quando la ricorsione raggiunge il caso base, la funzione termina, e i numeri vengono stampati nell’ordine corretto.

Esempi Pratici di Funzioni Ricorsive

1. Calcolo del Fattoriale

Uno degli esempi più classici di ricorsione è il calcolo del fattoriale di un numero, definito come:

n! = n * (n-1) * (n-2) * ... * 1
0! = 1

La funzione fattoriale può essere scritta ricorsivamente come segue:

def fattoriale(n):
    if n == 0:  # Caso base
        return 1
    else:
        return n * fattoriale(n - 1)  # Chiamata ricorsiva

print(fattoriale(5))  # Output: 120

Output:

In questo caso:

La funzione fattoriale continua a chiamarsi con n - 1 fino a raggiungere il caso base (n == 0).
Ogni chiamata restituisce il prodotto di n e il risultato della chiamata ricorsiva successiva.

2. Sequenza di Fibonacci

Un altro esempio classico è la sequenza di Fibonacci, dove ogni numero è la somma dei due numeri precedenti. La sequenza inizia con:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) per n > 1

Ecco una funzione ricorsiva per calcolare il numero di Fibonacci n-esimo:

def fibonacci(n):
    if n == 0:  # Caso base
        return 0
    elif n == 1:  # Caso base
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Chiamata ricorsiva

print(fibonacci(6))  # Output: 8

Output:

In questo esempio:

La funzione fibonacci richiama se stessa per calcolare i numeri di Fibonacci precedenti fino a raggiungere il caso base.

Vantaggi e Svantaggi della Ricorsione

Vantaggi

Semplicità: La ricorsione può semplificare la soluzione di problemi complessi che hanno una struttura naturale ricorsiva, come alberi, grafi e sequenze.
Eleganza: Spesso, le soluzioni ricorsive risultano più eleganti e più concise rispetto alle soluzioni iterative.

Svantaggi

Prestazioni: Le funzioni ricorsive possono essere meno efficienti delle soluzioni iterative, soprattutto se non sono ottimizzate con tecniche come la memorizzazione (memoization).
Stack Overflow: Le chiamate ricorsive consumano memoria nello stack di chiamate. Senza una condizione di uscita, si rischia di esaurire lo spazio dello stack, causando un errore di ricorsione infinita.

Esempio di Ricorsione Infinita

Un errore comune è non definire correttamente il caso base, che può causare una ricorsione infinita:

def ricorsione_infinita():
    return ricorsione_infinita()

ricorsione_infinita()  # Questo causerà un errore di RecursionError

Il programma sopra genererà un RecursionError poiché non c’è alcun caso base per terminare la ricorsione.

Ricorsione Ottimizzata: Memoization

In alcuni casi, come nel calcolo della sequenza di Fibonacci, la ricorsione può essere inefficiente, poiché lo stesso calcolo viene ripetuto più volte. Per risolvere questo problema, possiamo utilizzare la memoization, una tecnica che memorizza i risultati intermedi per evitare ricalcoli.

Ecco un esempio di Fibonacci ottimizzato con memoization utilizzando un dizionario:

def fibonacci_ottimizzato(n, memo={}):
    if n in memo:  # Verifica se il risultato è già stato calcolato
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fibonacci_ottimizzato(n - 1, memo) + fibonacci_ottimizzato(n - 2, memo)
        return memo[n]

print(fibonacci_ottimizzato(50))  # Output: 12586269025

In questo esempio:

La funzione fibonacci_ottimizzato memorizza i risultati già calcolati nel dizionario memo per evitare di ricalcolare gli stessi valori.

Ricorsione Vs Iterazione

Spesso un problema che può essere risolto con la ricorsione può anche essere risolto con un approccio iterativo, come i loop for o while. Ecco un confronto tra una soluzione ricorsiva e una iterativa per calcolare il fattoriale.

Ricorsione:

def fattoriale(n):
    if n == 0:
        return 1
    else:
        return n * fattoriale(n - 1)

Iterazione:

def fattoriale_iterativo(n):
    risultato = 1
    for i in range(1, n + 1):
        risultato *= i
    return risultato

In generale:

La ricorsione può essere più intuitiva per problemi che hanno una struttura naturale ricorsiva, come la traversata di alberi.
L’iterazione è generalmente più efficiente dal punto di vista delle prestazioni e meno soggetta a problemi di memoria.

Considerazioni Finali

Le funzioni ricorsive sono uno strumento potente e flessibile in Python. Sebbene possano essere meno efficienti delle soluzioni iterative in alcuni casi, la ricorsione offre una soluzione elegante e intuitiva per problemi che possono essere suddivisi in sotto-problemi più piccoli. Con una buona comprensione dei casi base e delle tecniche di ottimizzazione come la memoization, puoi sfruttare al meglio la ricorsione nei tuoi progetti Python.