In questo tutorial vedremo il Ricorsione con esempi in Python. La ricorsione in programmazione è una tecnica molto potente, si fa con funzioni che si richiamano, la vedono come una specie di loop, visto che lo stesso codice verrà ripetuto più volte, fino a raggiungere la soluzione.
Caratteristiche che deve avere una funzione ricorsivaCaso baseCi consentirà di terminare la funzione ad un certo punto e che non si verifichino chiamate infinite.
Caso ricorsivoIn questo caso chiamiamo nuovamente la funzione, ma ci avvicineremo alla soluzione. Sembrerà migliore negli esempi.
NotaÈ importante essere chiari sul caso base e sapere che il caso ricorsivo si sta avvicinando ad esso e non entra in uno stato di chiamate infinite, è un errore comune quando si inizia con la ricorsione.
Passiamo agli esempi, che saranno semplici e brevi in modo da poter essere ben assimilati.
Esempio 1 - Fattoriale
In questo esempio lo faremo risolvere il fattoriale di un numeroSe vuoi sapere di cosa tratta il fattoriale, visita questo link. Ecco il codice e di seguito spiego la funzione ricorsiva.
def fattoriale (numero): if (numero == 0 o numero == 1): return 1 else: restituisce numero * fattoriale (numero-1) if __name__ == "__main__": try: num = int (input ("Da Di quale numero vuoi conoscere il fattoriale? ")) if (num <0): print (" Il numero deve essere maggiore o uguale a 0 ") else: print (" Il fattoriale di ", num," è ", fattoriale (num )) tranne: print ("È previsto un numero") La nostra funzione ricorsiva ha il caso base nel if e quello ricorsivo nell'else. Puoi vedere che il caso base restituisce un 1 e che questo viene raggiunto quando il parametro passato alla funzione è 0 o 1, quando questo caso viene raggiunto la funzione non chiama di nuovo. Nel caso ricorsivo abbiamo una chiamata della funzione a se stessa, ma come puoi vedere riducendo il parametro di 1 (ci avviciniamo al caso base). L'ultima parte del codice al di fuori della funzione si occupa solo di chiedere all'utente un numero e di verificare che sia maggiore o uguale a 0 per chiamare la funzione, poiché il fattoriale con numeri negativi non funziona.
Se effettuiamo la chiamata alla funzione con il numero 4, cioè fattoriale (4), abbiamo le seguenti chiamate:
Chiamata 1: fattoriale (4) Chiamata 2: 4 * fattoriale (3) Chiamata 3: 3 * fattoriale (2) Chiamata 4: 2 * fattoriale (1)Quando si chiama fattoriale con 1, non ci sono più chiamate e restituirà 1, quindi questa funzione restituisce i risultati alla funzione che la chiamo, il ritorno sarebbe così:
fattoriale (1) = 1 fattoriale (2) = 2 * 1 fattoriale (3) = 3 * 2 fattoriale (4) = 4 * 6E abbiamo già il nostro risultato, che è 24, moltiplicando i numeri: 1 * 2 * 3 * 4. Successivamente lascio uno screenshot quando chiedo il fattoriale di 5, che non è altro che moltiplicare 5 per il fattoriale di 4 (che sappiamo già è 24) dando come risultato 120. Puoi anche vedere che se l'utente inserisce il numero sbagliato, è:
Esempio 2 - Addizione/Sottrazione
In questo esempio ho messo una funzione ricorsiva per fare un'addizione o una sottrazione, ovviamente questo esempio di solito non si verifica nella vita reale, ma come esempio funziona:
def operare (numero1, numero2): if (numero2 == 0): return numero1 elif (numero2 <0): return operare (numero1-1, numero2 + 1) else: return operare (numero1 + 1, numero2-1) if __name__ == "__main__": print ("Sommando 10 e 3:", opera (10, 3)) print ("Sommando 5 e -2:", opera (5, -2)) Qui abbiamo un caso base e 2 casi ricorsivi, questo per sapere da che parte toccare, poiché a seconda che il numero sia positivo o negativo dovremo agire diversamente. La funzione opera riceve 2 numeri, e l'algoritmo si occuperà di sottrarre o sommare uno a numero2 e di passarlo a numero1 (Se numero2 è positivo, sottraggo 1 da numero2 e lo aggiungo a numero1), quindi finché la variabile numero2 è uguale a 0.
Ad esempio andremo ad aggiungere 3 + 2 vedendo le chiamate.
Chiamata 1: opera (3,2) Chiamata 2: opera (4,1) Chiamata 3: opera (5,0)In questo caso, quando arriviamo ad operare (5,0) non c'è altro da fare, abbiamo il risultato direttamente (a differenza del fattoriale che doveva fare la moltiplicazione). Ecco il risultato dell'esecuzione del codice:
NotaSebbene con la ricorsione abbiamo una soluzione elegante e normalmente più corta dovrebbe essere usata quando non abbiamo altra opzione, se possiamo tirare dalla sua variante iterativa sarà una scelta migliore, poiché consuma meno memoria ed è solitamente più veloce.
Ti è piaciuto e hai aiutato questo Tutorial?Puoi premiare l'autore premendo questo pulsante per dargli un punto positivo
