Cos'è la funzione ricorsiva?
La funzione si chiama più e più volte fino a quando non soddisfa una condizione ricorsiva. Una funzione di ricorsione suddivide il problema in problemi più piccoli e chiama la propria logica per risolvere il problema più piccolo. Questa tecnica è nota come divisione e conquista. È usato in matematica e nel campo dell'informatica.
La funzione ricorsiva include un caso base (o un caso terminale) e un caso ricorsivo. Nel caso di base, è possibile considerare il problema principale da risolvere e il caso ricorsivo divide il problema in parti più piccole fino a quando non raggiunge un livello in cui può essere risolto prontamente. Un caso ricorsivo può restituire un risultato o può richiamare se stesso per dividere ulteriormente il problema. Ogni volta che il problema si scompone in un problema più piccolo, la funzione che viene chiamata salva in modo ricorsivo lo stato della chiamata e si aspetta il risultato da sé dopo aver risolto il problema.
Funzione ricorsiva in Python
Il concetto di ricorsione rimane lo stesso in Python. La funzione si chiama per scomporre il problema in problemi minori. L'esempio più semplice che potremmo pensare alla ricorsione sarebbe trovare il fattoriale di un numero.
Diciamo che dobbiamo trovare il fattoriale del numero 5 => 5! (Il nostro problema)
Per trovare 5! il problema può essere suddiviso in più piccoli 5! => 5 x 4!
Quindi, per ottenere 5! Dobbiamo trovarne 4! e moltiplicalo per 5.
Continuiamo a dividere il problema
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Quando raggiunge il pezzo più piccolo, cioè ottenendo il fattoriale di 1, possiamo restituire il risultato come
Facciamo un esempio di pseudo-codice: -
Algoritmo per fattoriale
Vediamo l'algoritmo per fattoriale:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Chiamate di funzione
Supponiamo di trovare un fattoriale di 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Il risultato finale sarà 120 dove abbiamo iniziato l'esecuzione della funzione. La nostra funzione di ricorsione si fermerà quando il numero è così ridotto da poter ottenere il risultato.
- La prima chiamata che sta ottenendo il fattoriale di 5 si tradurrà in una condizione ricorsiva in cui verrà aggiunta allo stack e verrà effettuata un'altra chiamata dopo aver ridotto il numero a 4.
- Questa ricorsione continuerà a chiamare e spezzare il problema in blocchi più piccoli fino a raggiungere la condizione di base.
- La condizione di base qui è quando il numero è 1.
- Ogni funzione ricorsiva ha una propria condizione ricorsiva e una condizione di base.
Pro e contro della funzione ricorsiva di Python
- L'esecuzione della ricorsione è tale da non eseguire alcun calcolo fino a quando non raggiunge la condizione di base.
- Nel raggiungere le condizioni di base potresti esaurire la memoria.
- In un grosso problema in cui possono esserci un milione di passaggi o si può dire che un milione di ricorsioni per eseguire il programma potrebbe finire per dare un errore di memoria o un errore di segmentazione.
- 1000000! = 1000000 * 999999! =?
- La ricorsione è diversa dall'iterazione che non si ingrandisce come un metodo iterativo.
- Lingue diverse hanno ottimizzazioni diverse per la ricorsione.
- In molte lingue, il metodo iterativo avrebbe prestazioni migliori della ricorsione.
- Ogni lingua ha alcune restrizioni sulla profondità della ricorsione che potresti incontrare quando risolvi grandi problemi.
- A volte è difficile comprendere i complessi problemi della ricorsione, mentre è piuttosto semplice con l'iterazione.
Alcuni professionisti
- In alcuni casi, la ricorsione è un modo comodo e veloce da usare.
- Molto utile nella traversata dell'albero e nella ricerca binaria.
Codice Python - Ricorsione vs Iterazione
Abbiamo capito cos'è la ricorsione e come funziona in Python, poiché sappiamo che tutte le lingue hanno implementazioni diverse della ricorsione per la memoria e le ottimizzazioni computazionali. Può esserci un caso in cui l'iterazione sarebbe più veloce della ricorsione.
Qui confronteremo sia il metodo di ricorsione che quello di iterazione per vedere come Python si comporta in entrambi i casi.
1. Codice di ricorsione per fattoriale
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Problema fattoriale mediante iterazione (loop)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Stampa dei risultati
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Produzione:
Come possiamo vedere entrambi danno lo stesso output di come abbiamo scritto la stessa logica. Qui non possiamo vedere alcuna differenza nell'esecuzione.
Aggiungiamo un po 'di time code per ottenere maggiori informazioni sull'esecuzione della ricorsione e dell'iterazione in Python.
Importeremo la libreria "time" e verificheremo a che ora ricorrono e iterazione per restituire il risultato.
4. Codice con calcolo del tempo
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Faremo ripetute esecuzioni con un valore diverso per fattoriale e vedremo i risultati. I risultati seguenti potrebbero variare da macchina a macchina. Abbiamo usato MacBook Pro 16 GB di RAM i7.
Stiamo usando Python 3.7 per l'esecuzione
Caso 1: - Fattoriale di 6:
Caso 2: fattoriale di 50:
Caso 3: fattoriale di 100:
Caso 4: Fattoriale di 500:
Caso 5: fattoriale di 1000:
Abbiamo analizzato entrambi i metodi in un problema diverso. Inoltre, entrambi hanno eseguito risultati simili, tranne il caso 4.
Nel caso 5 abbiamo riscontrato un errore durante la ricorsione.
Python ha una limitazione sulla profondità massima che puoi affrontare con la ricorsione, ma lo stesso problema sono stato in grado di risolverlo con iterazione.
Python ha delle restrizioni contro il problema dell'overflow. Python non è ottimizzato per la ricorsione della coda e la ricorsione incontrollata provoca un overflow dello stack.
La funzione "sys.getrecursionlimit ()" ti direbbe il limite per la ricorsione.
Il limite di ricorsione può essere modificato ma non raccomandato potrebbe essere pericoloso.
Conclusione - Funzione ricorsiva Python
- La ricorsione è una soluzione pratica per alcuni problemi come l'attraversamento di alberi e altri problemi.
- Python non è un linguaggio di programmazione funzionale e possiamo vedere che lo stack di ricorsione non è ottimizzato rispetto all'iterazione.
- Dovremmo usare l'iterazione nel nostro algoritmo poiché è più ottimizzata in Python e ti offre una maggiore velocità.
Articoli consigliati
Questa è una guida alla funzione ricorsiva in Python. Qui discutiamo Cos'è la funzione ricorsiva, la funzione ricorsiva in Python, l'algoritmo per fattoriale, ecc. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più–
- Fattoriale in Python
- Comandi Spark Shell
- I migliori compilatori C.
- Tipi di algoritmi
- Programma fattoriale in JavaScript
- Guida all'elenco dei comandi Unix Shell
- Tipi di forme in reazione con esempi