Concetti Chiave
- La ricorsione è una tecnica di programmazione che consente a una funzione di richiamare se stessa, sospendendo l'esecuzione fino al termine della nuova chiamata.
- Si distinguono due tipi di ricorsione: diretta, dove un algoritmo richiama sé stesso, e indiretta, dove due algoritmi si richiamano reciprocamente.
- La tecnica "divide et impera" suddivide un problema complesso in sottoproblemi più semplici risolti ricorsivamente, combinando i risultati finali con un approccio top-down.
- La ricorsione richiede l'individuazione di casi base, che permettono la terminazione immediata, e casi ricorsivi, che comportano il richiamo della funzione stessa.
- La ricorsione in coda (tail recursion) permette l'ottimizzazione delle chiamate ricorsive, riducendo l'uso dello stack attraverso la tail call elimination, supportata da alcuni compilatori.
Funzioni 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.
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.
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
- Che cos'è la ricorsione e come viene utilizzata in informatica?
- Qual è la differenza tra ricorsione diretta e ricorsione indiretta?
- Quali sono i vantaggi e gli svantaggi della ricorsione rispetto alle procedure iterative?
La ricorsione è un processo che permette di definire qualcosa richiamando se stessa. In informatica, è una tecnica di programmazione potente supportata da quasi tutti i linguaggi di alto livello, dove una funzione ricorsiva chiama se stessa, sospendendo l'esecuzione per eseguire la nuova chiamata.
La ricorsione diretta si verifica quando un algoritmo è espresso in termini di sé stesso, mentre la ricorsione indiretta o mutua ricorsione avviene quando due algoritmi si invocano reciprocamente.
La ricorsione è più dispendiosa in termini di efficienza rispetto a una procedura iterativa a causa dei record di attivazione. Tuttavia, la ricorsione in coda può essere ottimizzata tramite l'eliminazione delle chiamate in coda, riducendo l'uso dello stack e migliorando l'efficienza.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
