Ricorsione

Quando scriviamo programmi, di solito richiamiamo diverse funzioni per svolgere compiti molto specifici. Ad esempio, richiamiamo sqrt per calcolare la radice quadrata di un numero, oppure chiamiamo max o min per trovare il massimo o il minimo di un insieme di numeri. La ricorsione è il processo in cui la stessa funzione richiama se stessa. Quindi, se abbiamo implementato una funzione con il nome f, e in qualche punto all’interno del corpo di f invochiamo nuovamente f (di solito con argomenti diversi), questa è una chiamata ricorsiva:

def f(n):                                   # Definisce una funzione chiamata f
    print(f'f() called with argument {n}')  # Stampa ad ogni chiamata (a scopo dimostrativo)
    if n <= 0:                              # Si interrompe se n è negativo
        print('Let\'s stop here...')
    else:                                   # Altrimenti chiama f con un numero più piccolo
        f(n - 1)

f(10)

Ecco cosa stamperebbe il programma

f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...

Questo è un semplice esempio che dimostra come potrebbe essere implementata una funzione ricorsiva di base. In scenari più realistici, di solito eseguiamo calcoli all’interno delle funzioni e restituiamo valori, anziché limitarci a stampare messaggi.

Nei problemi di tipo algoritmico, la ricorsione può essere molto utile, specialmente quando si lavora con grafi, algoritmi avanzati di ordinamento o con tecniche di backtracking che tratteremo più avanti nel corso. I problemi ricorsivi sono molto comuni, e talvolta è molto più semplice implementare una soluzione ricorsiva rispetto a una iterativa basata sui cicli.

Video preview — Un video di Reducible - 5 Simple Steps for Solving Any Recursive Problem

Il processo di risolvere un grande problema suddividendolo ricorsivamente in problemi più piccoli, fino ad arrivare al caso più semplice/facile possibile, può essere compreso meglio con il concetto chiamato “salto di fede ricorsivo”.

Salto di fede ricorsivo

Quando si implementa una soluzione ricorsiva a un problema, in genere si crea una funzione che, a un certo punto, richiama se stessa. La parte in cui la funzione si richiama viene normalmente indicata come “chiamata ricorsiva”.

La grande utilità delle soluzioni ricorsive è che si può assumere che la funzione funzioni correttamente con argomenti semplici, e poi si implementa il comportamento corretto per gli argomenti più complessi. Analogamente a quando si chiamano altre funzioni come sqrt, max, abs, ecc., si può dare per scontato che la funzione funzioni per argomenti più piccoli/semplici e utilizzarli come base su cui costruire il risultato corrente.

💡

L’unico requisito è assicurarsi che la funzione arrivi al caso base (il caso più semplice). In caso contrario, la funzione ricorsiva continuerebbe a chiamarsi all’infinito e potrebbe generare un StackOverflow!

Come dimostrazione di come si possa avere un calcolo all’interno di una funzione ricorsiva, proviamo a calcolare la somma di tutti i numeri da 0, 1, 2, …, n dato un numero n.

Implementiamo la funzione sum passo dopo passo. Il primo passo è assicurarsi che la funzione funzioni correttamente per il caso più semplice (calcolare correttamente la somma per n pari a 0 o 1):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # Se n è 0 => la somma è 0
        return 0       # Interrompe l'esecuzione della funzione qui
    if n == 1:         # Se n è 1 => la somma è 1
        return 1       # Interrompe l'esecuzione della funzione qui

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (non abbiamo ancora implementato questa parte)

Con questa parte della funzione, possiamo già utilizzare il fatto che sum(0) restituirà sempre 0 in modo corretto, mentre sum(1) restituirà sempre 1. La funzione funzionerà correttamente anche se richiamiamo sum con argomenti 0 o 1 dall’interno di sum stessa.

Possiamo quindi fare un passo in più e implementare la funzione sum per n = 2 e n = 3, sfruttando i risultati di sum(1) e sum(0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # Se n è 2, aggiungiamo 2 al risultato di sum(1) implementato sopra
        return n + sum(1)  # oppure n + sum(n - 1)
    if n == 3:             # Se n è 3, aggiungiamo 3 al risultato di sum(2) implementato sopra
        return n + sum(2)  # oppure n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (non abbiamo ancora implementato questa parte)

In questo modo, è chiaro che la funzione sum funziona correttamente per i casi semplici come n uguale a 0, 1, 2 o 3.

Avendo questo, possiamo implementare la funzione per altri valori di n maggiori di 3. L’unico requisito è arrivare a quei valori più piccoli di n (0, 1, 2 o 3) quando richiamiamo la funzione sum da se stessa. Quindi, per valori più grandi di n, come 4, 5 o 6, ecc., possiamo implementare la funzione sum usando il fatto che per calcolare sum(4) possiamo aggiungere 4 al risultato di sum(3), mentre per calcolare sum(5) possiamo aggiungere 5 al risultato di sum(4):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # Per tutti gli altri casi (4, 5, 6, ...)
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

Gli elementi fondamentali di una funzione ricorsiva sono:

Caso base: Una condizione che interrompe la ricorsione. Senza questo, la funzione si richiamerebbe all’infinito, causando un loop infinito. Qui, è n == 0 e n == 1.

Passo ricorsivo: Dove la funzione richiama se stessa, di solito con un argomento diverso. Qui, è sum(n - 1).

Poiché le chiamate per n == 1, n == 2 e n == 3 sono esattamente le stesse di quando n == 4, n == 5, ecc., è possibile semplificare ulteriormente la funzione sum lasciando un solo caso base (per n == 0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

In questo modo, grazie al “salto di fede ricorsivo”, assumiamo/sappiamo che la funzione funzioni correttamente per casi più piccoli/semplici e costruiamo il resto della funzione sulla base di quei casi più semplici. Questo aiuta a capire come lavorano le funzioni ricorsive e come possono essere implementate.

💡

Chiamare la funzione ricorsivamente è come chiamare una funzione completamente diversa di cui siete assolutamente certi funzioni con gli argomenti passati.

Sfida

Implementa una funzione ricorsiva che calcoli n! modulo .

Input

L’input contiene un solo intero n (1 ≤ n ≤ 1000).

Output

Il programma deve stampare il risultato di n! modulo .

Esempi

Input	Output
5	120
10	3628800

Salto di fede ricorsivo

Sfida

Input

Output

Esempi

Constraints

To check your solution you need to sign in

Sign in to continue