Lezioni di Python – 6.6 La Ricorsione

La Ricorsione

La ricorsione è un concetto molto importante nella programmazione funzionale.

Un aspetto base della ricorsione è l’auto riferimento della funzione che richiama se stessa.

Un classico esempio di funzione implementabile ricorsivamente è la funzione fattoriale. Il fattoriale di un numero equivale al prodotto di tutti i numeri da 0 fino a quel numero specificato.

def factorial(x):
    if x == 1:
        return 1
    else:
        return x * factorial(x-1)

print(factorial(5)) 

eseguendo

>>>
120

Dal codice dell’esempio possiamo vedere che abbiamo una condizione if che differenzia due casi diversi, quando usare la ricorsione e quando non usarla. Il caso in cui la ricorsione non viene usata viene chiamato caso base, dove per il calcolo di quello step non viene richiesta alcuna ricorsione.

L’utilizzo di funzioni ricorsive, se implementate non correttamente (per esempio senza tenere conto del caso base) sono infinite e verranno interrotte solo dal lancio di una eccezione (RunTime Error). Quindi bisogna fare sempre attenzione prima di eseguirle.

Ricorsioni indirette

Le ricorsioni possono essere anche indirette. Una funzione può chiamarne una seconda che a sua volta richiama la prima, e così via.  Ma la stessa cosa può avvenire con più funzioni.

def is_even(x):
    if x == 0:
        return True
    else:
        return is_odd(x-1)

def is_odd(x):
    return not is_even(x)

print(is_odd(23))
print(is_even(23)) 

eseguendo

>>>
True
False

⇐ Vai a Lezione 6.5 – I decoratori

Vai a Lezione 6.7 – Set ⇒