Esempio classico e' la visita di un albero. Non ti posto il codice che e' un po complicato. Un albero e' una struttura definita di per se' ricorsivamente nel seguente modo

caso base) Una foglia e' un albero
caso ricorsivo) Un nodo che ha degli alberi come figli e' a sua volta un albero.

In genere, quando crei una funzione ricorsiva, devi distinguere un caso base, al quale si ferma la ricorsione, ed un caso ricorsivo, nel quale la funzione richiama se stessa.

Nel caso della visita dell'albero, la funzione viene pressappoco così

codice:
1:funzione visita(nodo n)
2:  stampa(n)
3:  se n è una foglia(caso base) fine;
4:  se n non e' una foglia (caso ricorsivo)
5:    per ogni m figlio di n
6:       visita(m)
Oltre a rendere spesso più semplici e leggibili gli algoritmi, la ricorsione ha il grande vantaggio di facilitare le dimostrazioni di correttezza degli algoritmi stessi.

Per verificare un algoritmo ricorsivo la dimostrazione segue due semplici passi

1)dimostrare che funziona nel caso base
2)presupponendo che per un gerico input funziona, dimostrare che funziona per quello subito più "grande"

Per spiegare cosa si intende per più grande torniamo all'esempio precedente. La dimostrazione del passo induttivo (2) diventa

Sia t un albero con figli che ha n come radice e t1, ..., tk
come sottoalberi figli di n. Presupposto che l'algoritmo funziona per t1,..., tk dimostrare che funziona anche per t.
Attenzione : il post contiene un bel po di imprecisioni.