Che cos’è la ricorsione in programmazione?

La ricorsione è una tecnica in cui una funzione definisce la propria soluzione chiamando sé stessa su istanze più piccole dello stesso problema. Per essere corretta deve sempre avere almeno un caso base, cioè una condizione che interrompe le chiamate ricorsive. Senza caso base la funzione non termina.

Qual è il ruolo del caso base?

Il caso base è la condizione in cui il problema è già risolto senza ulteriori chiamate ricorsive. Serve a fermare la ricorsione e a garantire che l’algoritmo termini. In genere rappresenta l’istanza più semplice del problema.

Cosa succede nello stack delle chiamate durante una ricorsione?

Ogni chiamata a funzione crea un frame nello stack con parametri, variabili locali e indirizzo di ritorno. Quando la funzione richiama sé stessa, i frame si accumulano finché si raggiunge il caso base; poi il controllo risale e i frame vengono rimossi in ordine inverso. Questo spiega perché la ricorsione usa memoria di stack.

Come descrivi la ricorsione del fattoriale?

Il fattoriale di n si definisce in modo ricorsivo come n moltiplicato per il fattoriale di n meno uno, con caso base uguale a uno quando n è zero o uno, secondo la convenzione usata. È un esempio classico perché ogni passo riduce il problema a uno più piccolo fino al caso base. La corrispondenza tra definizione matematica e funzione è molto diretta.

Perché Fibonacci è un esempio meno efficiente di ricorsione?

Nella formulazione ricorsiva classica, ogni chiamata genera due chiamate più piccole, quindi molti sottoproblemi vengono ricalcolati più volte. Questo rende l’esecuzione molto ridondante rispetto alla versione iterativa o a una versione ricorsiva con memoizzazione. Il punto critico non è la ricorsione in sé, ma l’albero delle chiamate troppo ampio.

Come funzionano le torri di Hanoi come problema ricorsivo?

Il problema si risolve spostando n meno uno dischi sul supporto ausiliario, poi muovendo il disco più grande e infine rispostando n meno uno dischi sul supporto finale. La ricorsione è naturale perché il problema su n dischi si riduce a due sottoproblemi identici su n meno uno dischi. Qui il caso base è il movimento di un solo disco.

Qual è la differenza tra ricorsione e iterazione?

La ricorsione esprime la soluzione tramite autochiamate, mentre l’iterazione usa un ciclo e uno stato aggiornato passo dopo passo. Spesso la ricorsione è più vicina alla definizione matematica del problema, ma può usare più memoria di stack. L’iterazione, invece, è spesso più efficiente e controllabile dal punto di vista delle risorse.

In che senso la ricorsione è legata al divide et impera?

Nel divide et impera si divide il problema in sottoproblemi più piccoli, li si risolve spesso ricorsivamente e poi si combinano le soluzioni. La ricorsione è quindi il meccanismo naturale con cui si implementa questa strategia. Algoritmi come mergesort ne sono un esempio tipico.

Perché nella ricorsione bisogna parlare di correttezza e terminazione?

Perché una funzione ricorsiva non basta che sia intuitiva: deve produrre il risultato giusto e deve fermarsi per ogni input ammesso. La correttezza si dimostra mostrando che il caso base è corretto e che il passo ricorsivo preserva la proprietà cercata. La terminazione si giustifica perché ogni chiamata riduce il problema verso il caso base.

Quando conviene usare la memoizzazione?

La memoizzazione conviene quando una ricorsione genera molti sottoproblemi uguali, che altrimenti verrebbero ricalcolati più volte. Memorizzando i risultati già ottenuti, si riduce drasticamente il numero di chiamate effettive. È una tecnica tipica della programmazione dinamica.

Come valuti spazio e tempo di una funzione ricorsiva?

Bisogna distinguere il costo delle chiamate e il costo dello stack. Anche se il codice è breve, ogni chiamata occupa spazio nel call stack, quindi la profondità della ricorsione influenza la memoria usata. Dal punto di vista del tempo, conta il numero totale di chiamate e l’eventuale ricalcolo di sottoproblemi.

Collega la ricorsione alla programmazione dinamica: qual è il passaggio concettuale?

La programmazione dinamica nasce spesso da una definizione ricorsiva con sottoproblemi sovrapposti. Il passaggio concettuale consiste nel riconoscere che gli stessi sottoproblemi vengono risolti molte volte e nel salvarne i risultati, con memoizzazione top-down oppure con una soluzione bottom-up. Quindi non si elimina la ricorsione per forza, ma si elimina la ridondanza.

Da dove conviene partire se mi chiedono la ricorsione all’orale?

Parti da definizione, caso base e terminazione, poi passa allo stack delle chiamate con un esempio semplice come il fattoriale.

Cosa ripasso se ho poco tempo?

Ripassa bene fattoriale, Fibonacci, torri di Hanoi, differenza con l’iterazione e il significato di memoizzazione.

Come la collego ad altri argomenti per fare una risposta più completa?

Collegala a divide et impera, stack delle chiamate e programmazione dinamica, perché sono i tre agganci più naturali all’esame.

Guida aggiornata: settembre 2026 · a cura di Skooly · tutte le guide · altre domande di programmazione

Domande d'esame sulla ricorsione: le 12 che escono davvero, con le risposte

Quando il docente ti chiede la ricorsione, di solito vuole vedere se sai definirla in modo rigoroso e se capisci davvero cosa succede durante l’esecuzione, non solo se sai scrivere un esempio. In particolare vuole che tu spieghi caso base, chiamata ricorsiva e ruolo dello stack delle chiamate, oltre ai vantaggi e ai limiti rispetto all’iterazione.

In due minuti: La ricorsione è una tecnica in cui una funzione risolve un problema chiamando sé stessa su sottoproblemi più piccoli, fino a raggiungere uno o più casi base che fermano l’esecuzione. Ogni chiamata crea un nuovo frame nello stack delle chiamate, con i suoi parametri e le sue variabili locali. È molto naturale per problemi definiti in modo ricorsivo, come fattoriale, Fibonacci o torri di Hanoi, e si collega spesso al divide et impera. Rispetto all’iterazione è spesso più elegante, ma può essere meno efficiente in memoria e talvolta in tempo, se genera chiamate ridondanti. La memoizzazione serve proprio a evitare il ricalcolo di sottoproblemi già risolti.

I termini che il prof si aspetta: ricorsione · caso base · chiamata ricorsiva · stack delle chiamate · frame di attivazione · fattoriale · Fibonacci · torri di Hanoi · divide et impera · memoizzazione.

Le domande che escono all'esame

Che cos’è la ricorsione in programmazione?

La ricorsione è una tecnica in cui una funzione definisce la propria soluzione chiamando sé stessa su istanze più piccole dello stesso problema. Per essere corretta deve sempre avere almeno un caso base, cioè una condizione che interrompe le chiamate ricorsive. Senza caso base la funzione non termina.

Cosa vuole sentire: Vuole una definizione rigorosa e il richiamo esplicito alla terminazione. Errore tipico: Dire solo che è “una funzione che richiama sé stessa”, senza parlare di caso base e terminazione.
Qual è il ruolo del caso base?

Il caso base è la condizione in cui il problema è già risolto senza ulteriori chiamate ricorsive. Serve a fermare la ricorsione e a garantire che l’algoritmo termini. In genere rappresenta l’istanza più semplice del problema.

Cosa vuole sentire: Vuole capire che il caso base non è un dettaglio, ma l’elemento che rende la ricorsione finita. Errore tipico: Pensare al caso base come a un semplice “if” opzionale, invece che come parte essenziale della correttezza.
Cosa succede nello stack delle chiamate durante una ricorsione?

Ogni chiamata a funzione crea un frame nello stack con parametri, variabili locali e indirizzo di ritorno. Quando la funzione richiama sé stessa, i frame si accumulano finché si raggiunge il caso base; poi il controllo risale e i frame vengono rimossi in ordine inverso. Questo spiega perché la ricorsione usa memoria di stack.

Cosa vuole sentire: Vuole che tu colleghi ricorsione ed esecuzione concreta sullo stack. Errore tipico: Confondere lo stack con un concetto astratto, senza saper descrivere push e pop dei frame.
Come descrivi la ricorsione del fattoriale?

Il fattoriale di n si definisce in modo ricorsivo come n moltiplicato per il fattoriale di n meno uno, con caso base uguale a uno quando n è zero o uno, secondo la convenzione usata. È un esempio classico perché ogni passo riduce il problema a uno più piccolo fino al caso base. La corrispondenza tra definizione matematica e funzione è molto diretta.

Cosa vuole sentire: Vuole un esempio semplice ma corretto, con la struttura base/ricorsione ben visibile. Errore tipico: Scrivere solo la formula senza spiegare perché è un esempio di ricorsione.
Perché Fibonacci è un esempio meno efficiente di ricorsione?

Nella formulazione ricorsiva classica, ogni chiamata genera due chiamate più piccole, quindi molti sottoproblemi vengono ricalcolati più volte. Questo rende l’esecuzione molto ridondante rispetto alla versione iterativa o a una versione ricorsiva con memoizzazione. Il punto critico non è la ricorsione in sé, ma l’albero delle chiamate troppo ampio.

Cosa vuole sentire: Vuole che tu sappia distinguere la ricorsione elegante dalla ricorsione inefficiente. Errore tipico: Dire che Fibonacci è “sempre lento perché è ricorsivo”, senza spiegare il problema dei sottoproblemi sovrapposti.
Come funzionano le torri di Hanoi come problema ricorsivo?

Il problema si risolve spostando n meno uno dischi sul supporto ausiliario, poi muovendo il disco più grande e infine rispostando n meno uno dischi sul supporto finale. La ricorsione è naturale perché il problema su n dischi si riduce a due sottoproblemi identici su n meno uno dischi. Qui il caso base è il movimento di un solo disco.

Cosa vuole sentire: Vuole un esempio di ricorsione strutturata e non solo una definizione astratta. Errore tipico: Descrivere solo i passaggi operativi senza mettere in evidenza la riduzione del problema.
Qual è la differenza tra ricorsione e iterazione?

La ricorsione esprime la soluzione tramite autochiamate, mentre l’iterazione usa un ciclo e uno stato aggiornato passo dopo passo. Spesso la ricorsione è più vicina alla definizione matematica del problema, ma può usare più memoria di stack. L’iterazione, invece, è spesso più efficiente e controllabile dal punto di vista delle risorse.

Cosa vuole sentire: Vuole un confronto concettuale e pratico, non solo sintattico. Errore tipico: Dire che sono equivalenti in tutto, senza menzionare stack e costo in memoria.
In che senso la ricorsione è legata al divide et impera?

Nel divide et impera si divide il problema in sottoproblemi più piccoli, li si risolve spesso ricorsivamente e poi si combinano le soluzioni. La ricorsione è quindi il meccanismo naturale con cui si implementa questa strategia. Algoritmi come mergesort ne sono un esempio tipico.

Cosa vuole sentire: Vuole il collegamento tra paradigma algoritmico e tecnica di programmazione. Errore tipico: Confondere divide et impera con semplice ricorsione, senza parlare di divisione, risoluzione e combinazione.
Perché nella ricorsione bisogna parlare di correttezza e terminazione?

Perché una funzione ricorsiva non basta che sia intuitiva: deve produrre il risultato giusto e deve fermarsi per ogni input ammesso. La correttezza si dimostra mostrando che il caso base è corretto e che il passo ricorsivo preserva la proprietà cercata. La terminazione si giustifica perché ogni chiamata riduce il problema verso il caso base.

Cosa vuole sentire: Vuole che tu abbia una visione da esame, non solo da esercizio di codice. Errore tipico: Concentrarsi solo sull’output dell’esempio senza ragionare su correttezza generale e terminazione.
Quando conviene usare la memoizzazione?

La memoizzazione conviene quando una ricorsione genera molti sottoproblemi uguali, che altrimenti verrebbero ricalcolati più volte. Memorizzando i risultati già ottenuti, si riduce drasticamente il numero di chiamate effettive. È una tecnica tipica della programmazione dinamica.

Cosa vuole sentire: Vuole che tu colleghi ricorsione, sottoproblemi sovrapposti e programmazione dinamica. Errore tipico: Pensare che la memoizzazione serva sempre, invece che nei casi con forte ridondanza.
Come valuti spazio e tempo di una funzione ricorsiva?

Bisogna distinguere il costo delle chiamate e il costo dello stack. Anche se il codice è breve, ogni chiamata occupa spazio nel call stack, quindi la profondità della ricorsione influenza la memoria usata. Dal punto di vista del tempo, conta il numero totale di chiamate e l’eventuale ricalcolo di sottoproblemi.

Cosa vuole sentire: Vuole che tu ragioni in termini di complessità, non solo di sintassi. Errore tipico: Dire che la ricorsione “costa poco perché è elegante”, ignorando memoria e numero di chiamate.
Collega la ricorsione alla programmazione dinamica: qual è il passaggio concettuale?

La programmazione dinamica nasce spesso da una definizione ricorsiva con sottoproblemi sovrapposti. Il passaggio concettuale consiste nel riconoscere che gli stessi sottoproblemi vengono risolti molte volte e nel salvarne i risultati, con memoizzazione top-down oppure con una soluzione bottom-up. Quindi non si elimina la ricorsione per forza, ma si elimina la ridondanza.

Cosa vuole sentire: Vuole un collegamento profondo tra tecnica ricorsiva e ottimizzazione algoritmica. Errore tipico: Ridurre la programmazione dinamica a “un altro nome della ricorsione”.

Fatti interrogare sulla ricorsione, come all'esame. Carica le tue dispense, le slide o le sbobine, scegli il livello università e Skoo ti fa queste domande a voce, con il rigore di un esame: ti incalza se sei vago e alla fine ti dà una pagella sui quattro criteri, con le frasi che hai detto. I primi 30 minuti sono gratis, senza carta. Simula l'esame sulla ricorsione

Le risposte vaghe che non passano

«È quando una funzione si richiama da sola.»: Meglio: È una tecnica in cui una funzione risolve un problema chiamando sé stessa su sottoproblemi più piccoli, fino a raggiungere un caso base che garantisce la terminazione.
«Il caso base è la condizione iniziale dell’algoritmo.»: Meglio: Il caso base è l’istanza più semplice del problema, risolvibile senza ulteriori chiamate ricorsive, e serve a fermare la ricorsione.
«Fibonacci è lento perché usa la ricorsione.»: Meglio: La versione ricorsiva classica di Fibonacci è inefficiente perché genera molti sottoproblemi sovrapposti e li ricalcola; con memoizzazione o iterazione si elimina questa ridondanza.

I collegamenti che fanno salire il voto

Algoritmi — divide et impera. La ricorsione è spesso il meccanismo con cui si implementa la strategia di dividere il problema, risolvere i sottoproblemi e combinare i risultati.
Strutture dati — stack. Ogni chiamata ricorsiva occupa un frame nello stack delle chiamate, quindi la ricorsione si capisce davvero solo collegandola alla struttura a pila.
Programmazione dinamica — memoizzazione. Molte ricorsioni inefficaci diventano efficienti quando si memorizzano i risultati dei sottoproblemi già risolti.

Come ti valuta la pagella sulla ricorsione

Un'interrogazione si valuta su quattro criteri. Ecco cosa fa la differenza in questo argomento:

Criterio	Cosa fa la differenza qui
Conoscenza dei contenuti	Fa la differenza saper definire la ricorsione in modo rigoroso, distinguendo chiaramente caso base, passo ricorsivo e terminazione.
Correttezza espositiva e lessico specifico	Premia chi spiega lo stack delle chiamate con ordine, usando i termini frame, chiamata e ritorno senza confonderli.
Capacità di analisi e collegamenti	Fa salire il voto chi sa confrontare ricorsione e iterazione anche sul piano della complessità e dei sottoproblemi sovrapposti.
Autonomia nell'argomentare	Il massimo si vede quando colleghi spontaneamente ricorsione, divide et impera e programmazione dinamica, scegliendo tu il caso in cui conviene usarla.

Criterio

Cosa fa la differenza qui

Conoscenza dei contenuti

Fa la differenza saper definire la ricorsione in modo rigoroso, distinguendo chiaramente caso base, passo ricorsivo e terminazione.

Correttezza espositiva e lessico specifico

Premia chi spiega lo stack delle chiamate con ordine, usando i termini frame, chiamata e ritorno senza confonderli.

Capacità di analisi e collegamenti

Fa salire il voto chi sa confrontare ricorsione e iterazione anche sul piano della complessità e dei sottoproblemi sovrapposti.

Autonomia nell'argomentare

Il massimo si vede quando colleghi spontaneamente ricorsione, divide et impera e programmazione dinamica, scegliendo tu il caso in cui conviene usarla.

Domande frequenti

Da dove conviene partire se mi chiedono la ricorsione all’orale?: Parti da definizione, caso base e terminazione, poi passa allo stack delle chiamate con un esempio semplice come il fattoriale.
Cosa ripasso se ho poco tempo?: Ripassa bene fattoriale, Fibonacci, torri di Hanoi, differenza con l’iterazione e il significato di memoizzazione.
Come la collego ad altri argomenti per fare una risposta più completa?: Collegala a divide et impera, stack delle chiamate e programmazione dinamica, perché sono i tre agganci più naturali all’esame.

Altre domande d'esame di programmazione

La complessità degli algoritmi · La programmazione a oggetti · Le basi di dati e SQL · Le strutture dati · Variabili, tipi e controllo del flusso · tutti gli argomenti di programmazione

Come si prepara un orale universitario: simulare l'esame orale · Skooly per l'università.

Le domande e le risposte modello di questa pagina sono generate con l'intelligenza artificiale a partire dal programma scolastico, passate da una verifica automatica dei fatti e riviste a campione dalla redazione di Skooly (AI Act, Art. 50). Hai trovato un errore? Scrivi a supporto@skooly.it e lo correggiamo.