Ricorsione: lo stesso disegno più piccolo

Un problema è un caso banale più lo stesso problema su un pezzo.

Il disegno

Dall’istanza grande al caso che sai risolvere a occhio.

pezzo selezionato

Problema n

Non lo risolvi in un colpo. Lo spezzi.

Da ricordare

Se non c’è riduzione, non è ricorsione: è un loop mascherato male.

Fattoriale è l’esempio noioso. Utile: alberi, divide-et-impera, backtracking. Lo stack cresce. Troppo fondo = boom.

Iterare è lo stesso lavoro con una pila esplicita. Se non vedi lo stack, comunque c’è.

Disegna questo

Un triangolo grande, due più piccoli sotto, quattro ancora sotto. Scrivi “caso base” sulle foglie.

Un foglio, non un software. Se lo sai ridisegnare senza guardare, la lezione è tua.