Qualche settimana fa sono stato contattato da un nuovo amico di nome Simone che mi chiedeva se potevo fornirgli maggiori spiegazioni sull'algoritmo di ricerca delle combinazioni che ho presentato qui.
Per spiegare l'algoritmo avevo bisogno di chiarire bene il funzionamento della ricorsione e per questo motivo gli ho scritto un piccolo esempio di base.
Anche se in rete si trova già moltissimo materiale sulla ricorsione, ho voluto pubblicare queste note in quanto sono state fondamentali per Simone e quindi, chissà, potrebbero aiutare anche altri!
L’esempio che solitamente si usa è quello del calcolo del fattoriale di un numero.
Il fattoriale di un numero naturale n, che si indica con n!, è il prodotto dei numeri interi positivi minori o uguali a tale numero.
Il calcolo si può eseguire molto semplicemente utilizzando un ciclo che va da 1 a n; un esercizio molto utile potrebbe essere quello di sviluppare la funzione fattoriale(n) in maniera iterativa (ovvero con un ciclo).
Un altro metodo è quello ricorsivo: tralasciando la parte matematica, che si può trovare spiegata in wikipedia e in altre migliaia di siti, possiamo dire che la funzione fattoriale dovrà ritornare:
- n * fattoriale(n-1) se n è maggiore di 0
- 1 se n è 0
Due considerazioni:
- si potrebbe gestire anche il caso di n == 1 in cui possiamo ritornare subito 1, senza richiamare fattoriale(0)… questione di gusti!
- aggiungiamo anche un caso in cui n sia minore di 0… non si sa mai!
Questo è il codice:
def fattoriale( val ):
if( val>0 ):
res = val * fattoriale(val-1)
elif( val==0 ):
res = 1;
else:
res = 0;
return res
if __name__ == "__main__":
print( "il fattoriale di 5 è "+str(fattoriale(5)))
Eseguendo il codice qui sopra si ottiene:
C:\...>python.exe fattoriale.py
il fattoriale di 5 è 120
Per capire questo algoritmo bisogna fare un significativo sforzo di astrazione; un’esecuzione step by step del codice (con un debugger, ad esempio) potrebbe aiutare ma, secondo me, non c’è niente di meglio che ottenere un “log” dell’esecuzione, anche semplicemente inserendo delle print().
A questo scopo va modificato il codice, qui sotto ho evidenziato le parti aggiunte a tale scopo:
def getmargin(level):
return " "*level
def fattorialeric( level, val ):
print( getmargin(level) + "fattorialeric: val=" + str(val))
if( val>0 ):
res = val * fattorialeric(level+1,val-1)
elif( val==0 ):
res = 1;
else:
res = 0;
print( getmargin(level) + "return " + str(res) )
return res
def fattoriale( val ):
return fattorialeric( 0, val )
if __name__ == "__main__":
print( "il fattoriale di 5 è "+str(fattoriale(5)))
Le modifiche sono:
- ho aggiunto una print() all’entrata e una print() all’uscita della funzione ricorsiva, in modo da capire la sequenza e il valore in input e il valore in output di ciascuna chiamata
- ho aggiunto una funzione, getmargin(level), che restituisce una riga di spazi dipendenti dal livello di chiamata, questo mi serve per ottenere un margine crescente e rendere l’idea delle chiamate ricorsive
- alla funzione ricorsiva ho aggiunto il parametro level, che faccio crescere ad ogni chiamata, così alle print() posso passare delle stringhe con un margine progressivo
- per non cambiare la chiamata a fattoriale(n) (ho aggiunto il parametro level e non voglio che chi mi chiama debba preoccuparsi di inizializzare tale valore) ho rinominato la funzione ricorsiva vera e propria in fattorialeric() e la nuova funzione fattoriale(n) si occupa semplicemente di richiamare la funzione ricorsiva passando level a 0.
Questo è il risultato:
C:\...>python.exe fattoriale.py
fattorialeric: val=5
fattorialeric: val=4
fattorialeric: val=3
fattorialeric: val=2
fattorialeric: val=1
fattorialeric: val=0
return 1
return 1
return 2
return 6
return 24
return 120
il fattoriale di 5 è 120
Spero che questo esempio possa aiutare quanti stanno avendo difficoltà nella comprensione della tecnica della ricorsione.
Buono studio!
