Vuoi imparare tutto sulla ricorsione nella programmazione? Questo tutorial sulla ricorsione in Python ti aiuterà a iniziare.
La ricorsione è una tecnica di risoluzione dei problemi estremamente utile da aggiungere alla casella degli strumenti del tuo programmatore. Sebbene inizialmente sia difficile capirlo, la ricorsione può aiutarti a trovare soluzioni più eleganti a problemi complessi.
In questo tutorial adotteremo un approccio basato sul codice per apprendere la ricorsione utilizzando Python. In particolare, tratteremo:
- Le basi della ricorsione
- Funzioni ricorsive e come funzionano
- Implementazione Python di funzioni ricorsive
- Differenze tra approccio iterativo e ricorsivo alla risoluzione dei problemi
Iniziamo!
Sommario:
Cos’è la ricorsione?
La ricorsione è una tecnica di programmazione in cui una funzione richiama se stessa ripetutamente per risolvere un problema.
Fondamentalmente, la ricorsione è un approccio di problem solving che implica la scomposizione di un problema complesso in sottoproblemi più piccoli e identici. Essenzialmente, consente di risolvere un problema in termini di versioni più semplici di se stesso.
Quindi, come implementiamo la ricorsione nel codice? Per fare ciò, capiamo come funzionano le funzioni ricorsive.
Comprendere le funzioni ricorsive
Definiamo una funzione ricorsiva che richiama se stessa all’interno della sua definizione. Ogni chiamata ricorsiva rappresenta una versione più piccola o più semplice del problema originale.
Per garantire che la ricorsione alla fine termini, le funzioni ricorsive devono includere uno o più casi base, ovvero condizioni in cui la funzione smette di chiamare se stessa e restituisce un risultato.
Analizziamolo ulteriormente. Una funzione ricorsiva è composta da:
- Caso base: il caso base è una condizione (o condizioni) che determina quando la ricorsione deve terminare. Quando il caso base viene soddisfatto, la funzione restituisce un risultato senza effettuare ulteriori chiamate ricorsive. Un caso base è essenziale per prevenire la ricorsione infinita.
- Caso ricorsivo: il caso ricorsivo definisce come suddividere il problema in sottoproblemi più piccoli. In questa parte della funzione, la funzione richiama se stessa con input modificati. Ogni chiamata ricorsiva è, quindi, un passo verso il raggiungimento del caso base.
Successivamente, parliamo di cosa succede quando chiami una funzione ricorsiva.
Come funziona la ricorsione dietro le quinte
Quando viene chiamata una funzione, un record del suo contesto di esecuzione viene inserito nello stack di chiamate. Questo record include informazioni sugli argomenti della funzione, sulle variabili locali e sulla posizione da restituire una volta terminata l’esecuzione della funzione.
Nel caso delle funzioni ricorsive, quando una funzione richiama se stessa, un nuovo record viene inserito nello stack di chiamate, sospendendo di fatto l’esecuzione della funzione corrente. Lo stack consente a Python di tenere traccia di tutte le chiamate di funzioni in sospeso, comprese quelle provenienti da chiamate ricorsive.
Finché non viene raggiunto il caso base, la ricorsione continua. Quando il caso base restituisce un risultato, le chiamate di funzione vengono risolte una per una, con ciascuna funzione che restituisce il risultato al livello precedente dello stack di chiamate. Questo processo continua fino al completamento della chiamata di funzione iniziale.
Implementazione della ricorsione in Python
In questa sezione esploreremo tre semplici esempi di ricorsione:
Per ogni esempio, indicheremo il problema, forniremo l’implementazione ricorsiva di Python e poi spiegheremo come funziona l’implementazione ricorsiva.
#1. Calcolo fattoriale mediante ricorsione
Problema: calcolare il fattoriale di un intero non negativo n, indicato come n!. Matematicamente, il fattoriale di un numero n è il prodotto di tutti gli interi positivi da 1 a n.
Il calcolo fattoriale si presta bene alla ricorsione, come mostrato:
Ecco la funzione ricorsiva per calcolare il fattoriale di un dato numero n:
def factorial(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Calcoliamo 5! utilizzando la funzione fattoriale():
factorial_5 = factorial(5) print(factorial(5)) # Output: 120
Ora vediamo come funziona la funzione:
- Abbiamo un caso base che controlla se n è uguale a 0 o 1. Se la condizione è soddisfatta, le funzioni restituiscono 1. Ricordiamolo 0! è 1, e quindi è 1!.
- Se n è maggiore di 1, calcoliamo n! moltiplicando n per il fattoriale di n-1. Questo è espresso come n * fattoriale(n – 1).
- La funzione continua a effettuare chiamate ricorsive con valori decrescenti di n finché non raggiunge il caso base.
#2. Numeri di Fibonacci con ricorsione
Problema: Trova il termine all’indice n-esimo nel Sequenza di Fibonacci. La sequenza di Fibonacci è definita come segue: F(0) = 0, F(1) = 1 e F(n) = F(n-1) + F(n-2) per n >= 2.
def fibonacciSeq(n):
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursion: F(n) = F(n-1) + F(n-2)
else:
return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)
Eseguiamo la funzione:
fib_5 = fibonacciSeq(5) print(fib_5) # Output: 5
Ecco come funziona la funzione:
- Cominciamo discutendo i casi base. Se n è 0, restituisce 0. E se n è 1, restituisce 1. Ricordiamo F(0) = 0 e F(1) = 1.
- Nel caso ricorsivo, se n è maggiore di 1, la funzione calcola F(n) sommando i termini F(n-1) e F(n-2). Questo è espresso come fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
- La funzione continua a effettuare chiamate ricorsive con valori decrescenti di n finché non raggiunge i casi base.
#3. Implementazione ricorsiva della ricerca binaria
Problema: implementare un algoritmo di ricerca binaria utilizzando la ricorsione per trovare la posizione di un elemento di destinazione in un elenco ordinato.
Ecco l’implementazione ricorsiva della ricerca binaria:
def binarySearch(arr, target, low, high):
# Base case: target not found
if low > high:
return -1
mid = (low + high) // 2
# Base case: target found
if arr[mid] == target:
return mid
# Recursive case: search left or right half of the array
elif arr[mid] > target:
return binarySearch(arr, target, low, mid - 1)
else:
return binarySearch(arr, target, mid + 1, high)
La funzione BinarySearch continua a dividere l’intervallo di ricerca a metà con ogni chiamata ricorsiva finché non trova la destinazione o determina che la destinazione non è nell’elenco.
Ecco un esempio di esecuzione della funzione:
arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96] target = 37 idx = binarySearch(arr, target, 0, len(arr)-1) print(idx) # Output: 4
Analizziamo cosa fa la funzione:
- Nell’implementazione ricorsiva della ricerca binaria, abbiamo due casi base. Innanzitutto, se il valore basso diventa maggiore di quello alto, significa che l’elemento di destinazione non è nell’elenco. Quindi restituiamo -1 per indicare che l’obiettivo non è stato trovato.
- L’altro caso base controlla se l’elemento all’indice centrale a metà dell’intervallo di ricerca corrente è uguale al target. Se corrispondono, restituiamo l’indice mid, indicando che abbiamo trovato l’obiettivo.
- Nel caso ricorsivo, se l’elemento centrale è maggiore dell’obiettivo, cerchiamo ricorsivamente la metà sinistra dell’array chiamando BinarySearch(arr, target, low, mid – 1). Se l’elemento centrale è inferiore all’obiettivo, cerchiamo la metà destra chiamando BinarySearch(arr, target, mid + 1, high).
Approccio ricorsivo e iterativo
L’approccio iterativo, ovvero l’utilizzo dei cicli, è un altro approccio comune alla risoluzione dei problemi. Quindi, in cosa differisce dalla ricorsione? Scopriamolo.
Innanzitutto, confrontiamo soluzioni ricorsive e iterative a un problema comune: calcolare il fattoriale di un numero.
Ecco l’implementazione ricorsiva del calcolo fattoriale:
def factorialRec(n):
# Base case
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n-1)!
else:
return n * factorial(n - 1)
Poiché sappiamo che il fattoriale di un numero non negativo è il prodotto di tutti i numeri da 1 a n, possiamo anche scrivere un’implementazione iterativa utilizzando i cicli.
def factorialIter(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
Entrambe queste implementazioni danno risultati identici.
factorial_5 = factorialRec(5) print(factorial_5) # Output: 120 factorial_5 = factorialIter(5) print(factorial_0) # Output: 120
Ma è preferibile un approccio iterativo rispetto alla ricorsione? Quando c’è una ricorsione profonda, con troppe chiamate di funzione, potresti incorrere in errori a causa del superamento della profondità di ricorsione. Il looping è un’opzione migliore per i problemi la cui implementazione ricorsiva richiede troppe chiamate di funzione per raggiungere il caso base.
Riassumiamo le differenze tra implementazioni iterative e ricorsive:
FunzionalitàApproccio ricorsivoApproccio iterativoStrutturaUtilizza chiamate di funzione ricorsive e si basa sullo stack di chiamate.Utilizza loop per l’iterazione senza chiamate di funzione aggiuntive.Casi baseRichiede casi base espliciti per interrompere la ricorsione.In genere utilizza condizioni di loop per la terminazione.PrestazioniPotrebbe essere meno efficiente in termini di memoria a causa dello stack di chiamate . La ricorsione profonda può talvolta portare a errori di overflow dello stack. Generalmente più efficiente in termini di memoria e meno incline a errori di overflow dello stack. Debug Può essere difficile da eseguire il debug a causa di più chiamate di funzione e contesti di esecuzione nidificati. Tipicamente più facile da eseguire il debug grazie a un flusso di esecuzione lineare e diretto .Approccio iterativo vs approccio ricorsivo
Conclusione
In questo articolo abbiamo iniziato imparando cos’è la ricorsione e come definire funzioni ricorsive con casi base e relazioni di ricorrenza.
Abbiamo quindi scritto del codice Python: implementazioni ricorsive di problemi di programmazione comuni. Infine, abbiamo appreso le differenze tra approcci iterativi e ricorsivi e i pro e i contro di ciascuno di questi approcci.
Successivamente, dai un’occhiata a questo elenco di domande per l’intervista a Python.