fattoriale ricorsivo

Il fattoriale ricorsivo

Spesso e volentieri, durante lo sviluppo dei nostri progetti, capita di utilizzare la ricorsione e per questo motivo, in questo nuovo articolo voglio parlarvi del fattoriale ricorsivo

Un metodo si dice ricorsivo quando all’interno della propria definizione compare una chiamata direttamente al metodo stesso. Questa forma di ricorsione si chiama ricorsione diretta

Esistono due requisiti, basilari, per essere sicuri che la ricorsione funzioni:

  • ogni invocazione ricorsiva deve semplificare in qualche modo l’elaborazione;
  • devono esistere casi speciali che gestiscano in modo diretto le elaborazioni più semplici;

Per quanto riguarda la mia più che personale opinione, utilizzare il metodo ricorsivo su algoritmi, come appunto il fattoriale ricorsivo, richiede uno studio un po’ più approfondito dell’informatica e del linguaggio che utilizziamo, anche se, come ricordo sempre, quest’ultimo non è altro che uno strumento con la quale mettiamo in pratica le nostre idee.

Come analizziamo un algoritmo ricorsivo ?

Come ho detto in precedenza, apriamo la mente e analizziamo il fattoriale:

Sappiamo che per definizione il fattoriale di 0 è uguale a 1 e il fattoriale di 1 è per forza di cose 1. 

Ora, grazie a queste osservazioni che possono sembrare più che banali, il fattoriale ricorsivo può essere definito in maniera matematica come :

fattoriale ricorsivo

In parole povere, se n, che non è altro che il numero che decidiamo del quale calcolare il fattoriale, è uguale a allora il fattoriale sarà 1 altrimenti la funzione ricorsiva calcola il fattoriale del numero n -1 moltiplicato per n finché n sarà uguale a 1.

Leggi articolo   Ordinare una lista di numeri

Graficamente

5!=5*4!

     4!=4*3!

          3!=3*2!

               2!=2*1!

                    1!=1

               2!=2*1=2

          3!=3*2=6

     4!=4*6=24

 

5!=5*24=120

Come possiamo vedere, il fattoriale di 5 è dato da 5 * il fattoriale di 4, e via così fino ad arrivare al fattoriale di 1

Implementiamo l'algoritmo e eseguiamo il debug

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

print(fatt(5))

				
			

Il codice si presenta molto compatto ottimizzato in maniera tale da evitare qualsiasi tipo di errore. Sono presenti le condizioni per le quali è possibile calcolare il fattoriale ed esse sono comprese all’interno delle condizioni if/else. 

Eseguendo il debug passo passo attraverso l’utilizzo dei breakpoint è possibile vedere in che modo il fattoriale viene calcolato. Il nostro editor richiamerà la funzione tante volte quanto indicato da n

I problemi della ricorsione

La ricorsione è una tecnica molto potente per decomporre problemi complessi, ma quando si scrivono programmi ricorsivi si incontrano tre problemi comuni: 

  • spazio sprecato: si scrivono metodi che contengono variabili locali non necessarie, oppure non usate, e così la memoria del sistema non è utilizzata in modo efficiente (lo spazio sprecato si moltiplica per il numero di invocazioni ricorsive effettuate);
  • ricorsione infinita: è un grave errore di programmazione che tipicamente si verifica perché manca la clausola di chiusura per terminare (errata gestione di anomalie) o perché i valori del parametro non si semplificano (errata gestione delle chiamate ricorsive);
  • complessità alta: per certi problemi le soluzioni ricorsive hanno complessità non lineare.

Altri possibili esercizi con la ricorsione

Come per tutti gli esercizi svolti consiglio di realizzarne altri in modo da rafforzare e consolidare il concetto di programmazione. Un programma facile da realizzare, oltre che al fattoriale ricorsivo, è la somma ricorsiva:

Leggi articolo   Socket Python 3.9 - Client e Server

” Scrivi una funzione somma( ) ricorsiva che accetta in ingresso un parametro n ed esegua la somma da 1 ad n.

La soluzione più semplice ed ottimizzata è questa:

				
					def somma(n):
    if n == 1:
        return n
    else:
        return n + somma(n - 1)
n = 5
print(somma(n))
				
			

Vediamo come con un semplice if/else è possibile realizzare degli algoritmi super efficaci e potenti. 

Per testare il funzionamento dell’algoritmo consiglio di scaricare un editor di testo come Visual Studio Code o usufruire degli editor online gratis che permettono, senza scaricare alcun tipo di file, di realizzare algoritmi e testarli. Dopo averne valutati alcuni, ho deciso di affidarmi a Repl.it, semplice, affidabile e potente.

Buon Coding : )

Condividi il post

Condividi su facebook
Condividi su google
Condividi su twitter
Condividi su email
Condividi su whatsapp