Concetti Chiave
- La ricorsione è una tecnica di programmazione in cui una funzione richiama se stessa, utile per risolvere problemi complessi in modo efficiente.
- Esistono due tipi di ricorsione: diretta, in cui un algoritmo si richiama, e indiretta, dove due algoritmi si invocano reciprocamente.
- La tecnica "divide et impera" suddivide un problema in sottoproblemi più semplici, risolvendo ciascuno ricorsivamente e combinando i risultati finali.
- Per implementare un algoritmo ricorsivo è necessario identificare casi base e casi ricorsivi, che determinano quando la funzione deve terminare o richiamarsi.
- La ricorsione in coda ottimizza l'allocazione di memoria eliminando i record di attivazione non necessari, aumentando l'efficienza delle chiamate ricorsive.
Ricorsione = processo che permette di definire qualcosa richiamando se stessa. In informatica la ricorsione è una tecnica di programmazione molto potente supportata da quasi tutti i linguaggi di alto livello. Quando una funzione ricorsiva chiama se stessa, sospende l’esecuzione ed esegue la nuova chiamata, l’esecuzione della precedente riprende quando la chiamata è terminata.
Tipi di ricorsione
Un algoritmo è un algoritmo espresso in termini di se stesso, parliamo di:
- ricorsione diretta: quando un algoritmo è espresso in termini di sè stesso
- ricorsione indiretta o mutua ricorsione: quando due algoritmi si invocano reciprocamente
Tecnica devide et impera = tecnica di programmazione in cui un problema è suddiviso in problemi più semplici, risolvendo quest’ultimi in modo ricorsivo e combinare infine i risultati per ottenere la soluzione finale, utilizzando un approccio top down. Ogni algoritmo ricorsivo può essere trasformato in un algoritmo iterativo e viceversa.
Casi base e ricorsivi
Per risolvere un algoritmo ricorsivo e necessario:
- individuare uno o piu casi base: insieme di operazioni per cui la funzione termina subito
- individuare uno o piu casi ricorsivi: insieme di operazioni per cui la funzione richiama se stessa
Attualmente la ricorsione è supportata da quasi tutti i linguaggi ad alto livello, mentre alcuni linguaggi funzione che non hanno strutture iterative usano solo la ricorsione, questi supportano un tipo di ricorsione chiamata ricorsione in coda (o tail recursion), implementabile efficientemente (tail call elimination) senza dover gestire tutte le chiamate ricorsive sullo stack.
In C è possibile usare la ricorsione anche con main() anche se e meglio non farlo.
Ogni chiamata comporta l’allocazione del record di attivazione sullo stack ma per ogni chiamata c’è la propria copia locale e i propri argomenti.
La ricorsione rispetto ad una procedura iterativa è più dispendiosa in termini di efficienza a causa dei record di attivazione.
Nel caso di ricorsione in coda, il valore di ritorno non è un’espressione ma è solo il valore restituito dalla chiamata ricorsiva, in questo caso i record di attivazione di ogni chiamata non sono essenziali e potrebbero essere eliminati dallo stack, poichè interessa solo il valore calcolato all’ultima chiamata ricorsiva, si può eseguire questa ottimizzazione (tail call elimination) che è supportata da alcuni compilatori.
Domande da interrogazione
- Qual è la definizione di ricorsione in informatica?
- Quali sono i tipi di ricorsione esistenti?
- Qual è la differenza tra ricorsione e iterazione in termini di efficienza?
La ricorsione è un processo che permette di definire qualcosa richiamando se stessa, ed è una tecnica di programmazione molto potente supportata da quasi tutti i linguaggi di alto livello.
Esistono due tipi di ricorsione: la ricorsione diretta, in cui un algoritmo è espresso in termini di se stesso, e la ricorsione indiretta o mutua, in cui due algoritmi si invocano reciprocamente.
La ricorsione è generalmente più dispendiosa in termini di efficienza rispetto a una procedura iterativa a causa dei record di attivazione, mentre la ricorsione in coda può essere ottimizzata tramite la tail call elimination, riducendo l'uso dello stack.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
