Ricorsione e backtracking

Cos'è la ricorsione?

La ricorsione è una tecnica di programmazione in cui una funzione si chiama da sola per risolvere un problema. Consente di suddividere un problema complesso in sottoproblemi più semplici.

Quali sono gli elementi fondamentali della ricorsione?

- Caso base - Caso ricorsivo

Cosa rappresenta il caso base?

Il caso base è una condizione che interrompe la ricorsione, fornendo una risposta diretta senza ulteriori chiamate alla funzione.

Vero o falso: la ricorsione deve sempre avere un caso base.

Vero, altrimenti si verifica un loop infinito e il programma andrà in overflow dello stack.

Esempio di funzione ricorsiva?

La funzione fattoriale: $\displaystyle fact(n) = n \times fact(n-1)$ se $\displaystyle n > 0$, altrimenti $\displaystyle fact(0) = 1$.

Qual è la differenza tra ricorsione e iterazione?

La ricorsione utilizza la chiamata di funzioni, mentre l'iterazione usa strutture di controllo come cicli per ripetere operazioni.

Come funziona la ricorsione?

La funzione si chiama ripetutamente con parametri modificati fino a raggiungere il caso base. Ogni chiamata viene aggiunta allo stack di chiamate.

Quali sono i vantaggi della ricorsione?

- Maggiore chiarezza del codice - Risoluzione naturale di problemi complessi - Facilità nel gestire strutture dati ricorsive come alberi

Cosa succede senza caso base?

Si genera un overflow dello stack, poiché la funzione continua a chiamarsi indefinitamente senza mai fermarsi.

Esempio di caso ricorsivo?

Per calcolare la somma dei primi n numeri naturali: $\displaystyle S(n) = n + S(n-1)$ se $\displaystyle n > 0$, altrimenti $\displaystyle S(0) = 0$.

Qual è il limite della ricorsione?

Il limite è imposto dalla dimensione dello stack di chiamate, che può causare un errore di stack overflow se la profondità è eccessiva.

Quando è preferibile usare la ricorsione?

Quando il problema è naturalmente ricorsivo, ad esempio nel caso di alberi o algoritmi di ricerca come la ricerca binaria.

Quali sono gli svantaggi della ricorsione?

- Maggiore consumo di memoria - Possibile inefficienza rispetto all'iterazione - Maggiore complessità nella gestione degli errori

Vero o falso: la ricorsione è sempre più efficiente dell'iterazione.

Falso, la ricorsione può essere meno efficiente a causa dell'overhead delle chiamate di funzione e dell'uso della memoria.

Cosa si intende per chiamata ricorsiva?

È una chiamata che avviene all'interno di una funzione alla stessa funzione, per affrontare una versione più semplice del problema originale.

Qual è un uso comune della ricorsione?

La ricerca e la traversata di strutture dati ad albero, come nei percorsi di un albero binario.

Tecnica di backtracking

Il backtracking è un metodo di ricerca che esplora tutte le possibilità per risolvere un problema, tornando indietro quando una soluzione parziale non è valida.

Vantaggi del backtracking

- Semplicità di implementazione - Efficace per problemi come il Sudoku - Trova tutte le soluzioni possibili

Utilizzo del backtracking

Quando la soluzione richiede di esplorare più scelte, come nei problemi di combinatoria o nei giochi.

Esempio di problema di backtracking

Il problema delle N regine: posizionare N regine su una scacchiera N x N senza che si attacchino.

Backtracking vs Ricorsione

Il backtracking è un tipo di ricorsione che torna indietro per esplorare nuove soluzioni.

Condizione di successo nel backtracking

Una soluzione è considerata valida se soddisfa tutti i vincoli del problema.

Domanda sull'implementazione

Come implementare il backtracking in Python? Utilizza una funzione ricorsiva che esplora le scelte e verifica le condizioni.

Complessità del backtracking

La complessità può essere esponenziale in funzione delle scelte, quindi non sempre è efficiente.

Esempio di codice di backtracking

```python # Funzione per trovare tutte le combinazioni def backtrack(soluzione): if condizione_di_fine: return soluzione for scelta in possibili_scelte: backtrack(soluzione + [scelta]) ```

Strategia di esplorazione nel backtracking

Le scelte possono essere esplorate in modo sistematico o in modo generativo, a seconda del problema.

Vero o falso: il backtracking è sempre ottimale.

Falso: il backtracking non garantisce la soluzione ottimale, solo tutte le possibili soluzioni.

Backtracking e vincoli

Il backtracking è utile per problemi con restrizioni, come il problema del cammino del grafo.

Cosa è il pruning?

Tecnica per ridurre lo spazio di ricerca eliminando scelte che non possono portare a una soluzione valida.

Applicazione classica del backtracking

Find Hamiltonian Path: trovare un percorso che visiti ogni vertice di un grafo esattamente una volta.

Cosa risolve la ricerca di cammini?

La ricerca di cammini risolve problemi di individuazione del percorso più breve in grafo, come nel GPS.

Esempio di problema di Sudoku?

Completare una griglia 9x9 rispettando le regole. Uso di backtracking per provare diverse combinazioni.

Vero o falso: La ricorsione è usata per la generazione di permutazioni.

Vero. La ricorsione facilita la creazione di tutte le permutazioni di un insieme di elementi.

Cosa fa un algoritmo di backtracking nel problema delle N regine?

Cerca di posizionare N regine su una scacchiera N×N senza conflitti. Prova combinazioni e torna indietro se necessario.

Completa: La ricorsione è utile per _____.

risolvere problemi che possono essere scomposti in sottoproblemi simili.

Differenza tra ricorsione e iterazione?

- Ricorsione: chiamate a funzione. - Iterazione: loop. Entrambi risolvono problemi, ma con approcci diversi.

Esempio di problema di combinazioni?

Generare tutte le combinazioni di un insieme. Utilizza la ricorsione per esplorare le scelte.

Cosa otteniamo utilizzando backtracking nel problema del labirinto?

Troviamo un percorso dalla partenza all'arrivo, esplorando e tornando indietro se le strade non sono valide.

Applicazione della ricorsione nella ricerca binaria?

La ricerca binaria divide l'array in metà e cerca l'elemento in modo ricorsivo, riducendo il problema.

Perché il backtracking è efficace nella risoluzione di problemi di scelta?

Permette di esplorare tutte le possibilità e tornare sui propri passi quando si raggiungono soluzioni non valide.