🔄 Funzioni Ricorsive e Decoratori

Scopri come le funzioni possono chiamare sé stesse e come estenderne le funzionalità con i decoratori

🎯 Funzioni Ricorsive

Le funzioni ricorsive sono funzioni che chiamano sé stesse per risolvere problemi che possono essere suddivisi in sotto-problemi più piccoli.

📝 Struttura di una funzione ricorsiva:

  1. Caso base → la condizione che interrompe la ricorsione (evita chiamate infinite)
  2. Caso ricorsivo → la funzione richiama sé stessa con un problema più piccolo

🔢 Esempio 1: Calcolare il Fattoriale

Il fattoriale di un numero è il prodotto di tutti i numeri interi positivi minori o uguali a quel numero.

La formula matematica è: n! = n × (n-1)!

Definizione: 0! = 1 (caso base), 5! = 5 × 4!, 4! = 4 × 3!, …

Implementazione Ricorsiva
def fattoriale(n):
    """
    Calcola il fattoriale di un numero in modo ricorsivo.
    
    Parametri:
    - n (int): Numero intero positivo di cui calcolare il fattoriale.
    
    Ritorna:
    - int: Fattoriale di n.
    """
    if n == 0:
        return 1  # Caso base: il fattoriale di 0 è 1
    return n * fattoriale(n - 1)  # Caso ricorsivo: n × (n-1)!

# Test della funzione
print(fattoriale(5))  # Output: 120
print(fattoriale(0))  # Output: 1
print(fattoriale(3))  # Output: 6

💡 Spiegazione dettagliata:

  • Se n == 0, restituisce 1 perché per definizione 0! = 1
  • Se n > 0, la funzione chiama sé stessa con n-1, moltiplicando i risultati
  • La chiamata ricorsiva continua finché n non diventa 0 (caso base)

🔢 Esempio 2: Serie di Fibonacci

La Serie di Fibonacci è una successione numerica in cui ogni numero è la somma dei due precedenti:

F(n) = F(n-1) + F(n-2)

Valori iniziali: F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, …

Implementazione Base
def fibonacci(n):
    """
    Calcola il numero di Fibonacci alla posizione n in modo ricorsivo.
    
    Parametri:
    - n (int): La posizione nella serie di Fibonacci.
    
    Ritorna:
    - int: Il numero di Fibonacci corrispondente.
    """
    if n == 0:
        return 0  # Caso base 1
    elif n == 1:
        return 1  # Caso base 2
    return fibonacci(n - 1) + fibonacci(n - 2)  # Somma i due numeri precedenti

# Test della funzione
print(fibonacci(7))  # Output: 13
print(fibonacci(5))  # Output: 5
print(fibonacci(10)) # Output: 55

💡 Spiegazione dettagliata:

  • Se n == 0, la funzione restituisce 0
  • Se n == 1, la funzione restituisce 1
  • Per n > 1, la funzione calcola F(n-1) + F(n-2), sommandoli

⚠️ Problema di Performance:

Questa versione è lenta per valori grandi di n perché ripete calcoli già effettuati.

➡ Soluzione: Ottimizziamola con la tecnica di memoization usando un decoratore.

🎭 Decoratori in Python

Un decoratore è una funzione che modifica il comportamento di un’altra funzione senza alterarne il codice originale.

✅ Utilizzi comuni dei decoratori:

  • Misurazione del tempo di esecuzione
  • Caching (salvataggio dei risultati per evitare ricalcoli)
  • Controllo accessi e autorizzazioni
  • Logging e debugging

⚡ Esempio 3: Fibonacci Ottimizzato con Decoratore

Ottimizziamo il calcolo di Fibonacci usando un decoratore per caching (functools.lru_cache).

Implementazione Ottimizzata
from functools import lru_cache

@lru_cache(maxsize=None)  # Memorizza i risultati per evitare ricalcoli
def fibonacci_ottimizzato(n):
    """
    Calcola il numero di Fibonacci alla posizione n in modo efficiente.
    
    Parametri:
    - n (int): La posizione nella serie di Fibonacci.
    
    Ritorna:
    - int: Il numero di Fibonacci corrispondente.
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fibonacci_ottimizzato(n - 1) + fibonacci_ottimizzato(n - 2)

# Test della funzione ottimizzata
print(fibonacci_ottimizzato(35))  # Output: 9227465 (molto veloce)
print(fibonacci_ottimizzato(40))  # Output: 102334155 (istantaneo)

💡 Spiegazione dettagliata:

  • @lru_cache(maxsize=None): memorizza i risultati delle chiamate precedenti per riutilizzarli
  • Velocità: la funzione evita di ripetere gli stessi calcoli, rendendola molto più rapida
  • maxsize=None: memorizza tutti i risultati senza limiti di dimensione

🛠️ Esercitazione Guidata

📝 Esercizio: Somma degli elementi di una lista

Scrivi una funzione somma_lista(lista) che calcoli la somma di tutti gli elementi di una lista usando la ricorsione, senza usare sum().

📋 Passaggi suggeriti:

  1. Se la lista è vuota, restituisci 0 (caso base)
  2. Se la lista ha elementi, somma il primo elemento al risultato della chiamata ricorsiva sulla lista rimanente
Soluzione
def somma_lista(lista):
    """
    Calcola la somma degli elementi di una lista usando la ricorsione.
    
    Parametri:
    - lista (list): Lista di numeri da sommare.
    
    Ritorna:
    - int/float: Somma degli elementi della lista.
    """
    if not lista:  # Se la lista è vuota
        return 0   # Caso base: somma di lista vuota è 0
    # Caso ricorsivo: primo elemento + somma del resto della lista
    return lista[0] + somma_lista(lista[1:])

# Test della funzione
print(somma_lista([1, 2, 3, 4, 5]))    # Output: 15
print(somma_lista([10, 20, 30]))       # Output: 60
print(somma_lista([]))                 # Output: 0

🎯 10 Tracce di Esercizi con Soluzioni

1️⃣ Contare le occorrenze di un carattere in una stringa

Soluzione
def conta_occorrenze(stringa, carattere):
    """
    Conta quante volte un carattere compare in una stringa usando la ricorsione.
    
    Parametri:
    - stringa (str): La stringa in cui cercare.
    - carattere (str): Il carattere da contare.
    
    Ritorna:
    - int: Numero di occorrenze del carattere.
    """
    if not stringa:  # Caso base: stringa vuota
        return 0
    # Caso ricorsivo: 1 se il primo carattere matcha, più il conteggio nel resto
    return (1 if stringa[0] == carattere else 0) + conta_occorrenze(stringa[1:], carattere)

# Test
print(conta_occorrenze("programmazione", "a"))  # Output: 3
print(conta_occorrenze("python", "z"))          # Output: 0

2️⃣ Merge Sort (ordinamento ricorsivo)

Soluzione
def merge_sort(lista):
    """
    Ordina una lista usando l'algoritmo Merge Sort ricorsivo.
    
    Parametri:
    - lista (list): Lista da ordinare.
    
    Ritorna:
    - list: Lista ordinata.
    """
    if len(lista) <= 1:
        return lista  # Caso base: lista vuota o con un elemento è già ordinata
    
    metà = len(lista) // 2
    sinistra = merge_sort(lista[:metà])   # Ordina la prima metà
    destra = merge_sort(lista[metà:])     # Ordina la seconda metà
    
    # Unisce le due metà ordinate
    return unisci(sinistra, destra)

def unisci(sinistra, destra):
    """Unisce due liste ordinate in una lista ordinata."""
    risultato = []
    i = j = 0
    
    while i < len(sinistra) and j < len(destra):
        if sinistra[i] <= destra[j]:
            risultato.append(sinistra[i])
            i += 1
        else:
            risultato.append(destra[j])
            j += 1
    
    # Aggiungi gli elementi rimanenti
    risultato.extend(sinistra[i:])
    risultato.extend(destra[j:])
    return risultato

# Test
print(merge_sort([64, 34, 25, 12, 22, 11, 90]))  # Output: [11, 12, 22, 25, 34, 64, 90]

3️⃣ Invertire una stringa

Soluzione
def inverti_stringa(s):
    """
    Inverte una stringa usando la ricorsione.
    
    Parametri:
    - s (str): Stringa da invertire.
    
    Ritorna:
    - str: Stringa invertita.
    """
    if len(s) <= 1:
        return s  # Caso base: stringa vuota o con un carattere
    # Caso ricorsivo: ultimo carattere + inversione del resto
    return inverti_stringa(s[1:]) + s[0]

# Test della funzione
print(inverti_stringa("python"))    # Output: "nohtyp"
print(inverti_stringa("hello"))     # Output: "olleh"
print(inverti_stringa("a"))         # Output: "a"

💡 Spiegazione: La funzione prende l'ultimo carattere (s[0]) e lo mette alla fine della stringa invertita del resto (s[1:]).
Il processo continua ricorsivamente finché non rimane un solo carattere.

4️⃣ Potenza di un numero

Soluzione
def potenza(base, esp):
    """
    Calcola la potenza di un numero usando la ricorsione.
    
    Parametri:
    - base (int/float): Base della potenza.
    - esp (int): Esponente (numero intero non negativo).
    
    Ritorna:
    - int/float: Risultato della potenza.
    """
    if esp == 0:
        return 1  # Caso base: qualsiasi numero elevato a 0 è 1
    # Caso ricorsivo: base * base^(esp-1)
    return base * potenza(base, esp - 1)

# Test della funzione
print(potenza(2, 3))    # Output: 8
print(potenza(5, 2))    # Output: 25
print(potenza(10, 0))   # Output: 1
print(potenza(3, 4))    # Output: 81

💡 Spiegazione: La funzione sfrutta la proprietà matematica che base^esp = base × base^(esp-1).
Il caso base è quando l'esponente è 0, dove qualsiasi numero elevato a 0 restituisce 1.

5️⃣ Trovare il massimo in una lista

Soluzione
def massimo_lista(lista):
    """
    Trova il valore massimo in una lista usando la ricorsione.
    
    Parametri:
    - lista (list): Lista di numeri.
    
    Ritorna:
    - int/float: Valore massimo nella lista.
    """
    if len(lista) == 1:
        return lista[0]  # Caso base: lista con un solo elemento
    
    # Caso ricorsivo: confronta il primo elemento con il massimo del resto
    max_del_resto = massimo_lista(lista[1:])
    return lista[0] if lista[0] > max_del_resto else max_del_resto

# Test della funzione
print(massimo_lista([3, 1, 4, 1, 5, 9, 2]))  # Output: 9
print(massimo_lista([-5, -2, -10, -1]))      # Output: -1
print(massimo_lista([42]))                   # Output: 42

💡 Spiegazione: La funzione confronta ricorsivamente il primo elemento con il massimo del resto della lista.
Quando la lista ha un solo elemento, quel elemento è il massimo (caso base).

6️⃣ Contare le cifre di un numero

Soluzione
def conta_cifre(n):
    """
    Conta il numero di cifre in un numero intero usando la ricorsione.
    
    Parametri:
    - n (int): Numero di cui contare le cifre.
    
    Ritorna:
    - int: Numero di cifre.
    """
    if n < 0:
        return conta_cifre(-n)  # Gestione numeri negativi
    if n < 10:
        return 1  # Caso base: numero con una cifra
    
    # Caso ricorsivo: 1 + conteggio cifre del numero senza l'ultima cifra
    return 1 + conta_cifre(n // 10)

# Test della funzione
print(conta_cifre(12345))    # Output: 5
print(conta_cifre(7))        # Output: 1
print(conta_cifre(0))        # Output: 1
print(conta_cifre(-987))     # Output: 3

💡 Spiegazione: La funzione rimuove l'ultima cifra dividendo per 10 (n // 10) e conta ricorsivamente.
Il caso base è quando il numero è minore di 10 (ha una sola cifra). Gestisce anche i numeri negativi.

7️⃣ Somma delle cifre di un numero

Soluzione
def somma_cifre(n):
    """
    Calcola la somma delle cifre di un numero usando la ricorsione.
    
    Parametri:
    - n (int): Numero di cui sommare le cifre.
    
    Ritorna:
    - int: Somma delle cifre.
    """
    if n < 0:
        return somma_cifre(-n)  # Gestione numeri negativi
    if n == 0:
        return 0  # Caso base: numero 0
    
    # Caso ricorsivo: ultima cifra + somma delle cifre rimanenti
    return (n % 10) + somma_cifre(n // 10)

# Test della funzione
print(somma_cifre(12345))    # Output: 15 (1+2+3+4+5)
print(somma_cifre(987))      # Output: 24 (9+8+7)
print(somma_cifre(0))        # Output: 0
print(somma_cifre(-456))     # Output: 15 (4+5+6)

💡 Spiegazione: La funzione estrae l'ultima cifra con n % 10 e somma ricorsivamente con le cifre rimanenti (n // 10).
Il caso base è quando il numero è 0. Gestisce anche i numeri negativi.

8️⃣ Verificare se una stringa è un palindromo

Soluzione
def is_palindromo(s):
    """
    Verifica se una stringa è un palindromo usando la ricorsione.
    
    Parametri:
    - s (str): Stringa da verificare.
    
    Ritorna:
    - bool: True se la stringa è un palindromo, False altrimenti.
    """
    # Pulisci la stringa (rimuovi spazi e converti in minuscolo)
    s = s.replace(" ", "").lower()
    
    if len(s) <= 1:
        return True  # Caso base: stringa vuota o con un carattere
    
    # Caso ricorsivo: primo e ultimo carattere uguali e il resto è palindromo
    if s[0] != s[-1]:
        return False
    return is_palindromo(s[1:-1])

# Test della funzione
print(is_palindromo("radar"))        # Output: True
print(is_palindromo("python"))       # Output: False
print(is_palindromo("Amore Roma"))   # Output: True
print(is_palindromo("a"))            # Output: True
print(is_palindromo(""))             # Output: True

💡 Spiegazione: La funzione confronta il primo e l'ultimo carattere. Se sono uguali, verifica ricorsivamente se la sottostringa interna è un palindromo.
Il caso base è quando la stringa ha 0 o 1 carattere (sempre palindromo). Gestisce anche spazi e maiuscole/minuscole.

9️⃣ Moltiplicazione ricorsiva

Soluzione
def moltiplica(a, b):
    """
    Moltiplica due numeri interi usando la ricorsione e l'addizione.
    
    Parametri:
    - a (int): Primo numero.
    - b (int): Secondo numero.
    
    Ritorna:
    - int: Prodotto di a e b.
    """
    if b == 0:
        return 0  # Caso base: qualsiasi numero moltiplicato per 0 è 0
    if b < 0:
        return -moltiplica(a, -b)  # Gestione numeri negativi
    
    # Caso ricorsivo: a + a × (b-1)
    return a + moltiplica(a, b - 1)

# Test della funzione
print(moltiplica(5, 3))    # Output: 15
print(moltiplica(7, 4))    # Output: 28
print(moltiplica(0, 5))    # Output: 0
print(moltiplica(6, -2))   # Output: -12
print(moltiplica(-3, 4))   # Output: -12

💡 Spiegazione: La funzione implementa la moltiplicazione come addizione ripetuta.
a × b = a + a × (b-1). Il caso base è quando b è 0. Gestisce anche i numeri negativi.

🔟 Ricerca binaria ricorsiva

Soluzione
def ricerca_binaria(lista, target, inizio=0, fine=None):
    """
    Cerca un elemento in una lista ordinata usando la ricerca binaria ricorsiva.
    
    Parametri:
    - lista (list): Lista ordinata in cui cercare.
    - target: Elemento da trovare.
    - inizio (int): Indice di inizio della ricerca.
    - fine (int): Indice di fine della ricerca.
    
    Ritorna:
    - int: Indice dell'elemento se trovato, -1 altrimenti.
    """
    if fine is None:
        fine = len(lista) - 1
    
    if inizio > fine:
        return -1  # Caso base: elemento non trovato
    
    mezzo = (inizio + fine) // 2
    
    if lista[mezzo] == target:
        return mezzo  # Elemento trovato
    elif lista[mezzo] > target:
        # Cerca nella metà sinistra
        return ricerca_binaria(lista, target, inizio, mezzo - 1)
    else:
        # Cerca nella metà destra
        return ricerca_binaria(lista, target, mezzo + 1, fine)

# Test della funzione
numeri = [1, 3, 5, 7, 9, 11, 13, 15]
print(ricerca_binaria(numeri, 7))    # Output: 3
print(ricerca_binaria(numeri, 1))    # Output: 0
print(ricerca_binaria(numeri, 15))   # Output: 7
print(ricerca_binaria(numeri, 8))    # Output: -1 (non trovato)

💡 Spiegazione: La ricerca binaria divide ricorsivamente la lista a metà. Se l'elemento al centro è il target, restituisce l'indice.
Se è maggiore, cerca nella metà sinistra; se è minore, cerca nella metà destra. Molto efficiente per liste ordinate (O(log n)).

Torna in alto