ricorsione

[Hall999]

Sapete dove posso trovare un testo che spieghi in modo chiaro e sintetico che mi permetta di usare con sufficienza la ricorsione nel giro di un pomeriggio?, ad oggi non riesco a implementare con naturalezza funzioni ricorsive, mi viene naturale risolvere un determinato problema in modo sequenziale.

[Manbearpig]

Un' esempio:
Hai un albero genealogico di una famiglia, per semplificare ammettiamo che vi sia inserito solo un genitore e un solo figlio per genitore. Vuoi trovare tutti gli antenati di un figlio come fai?

funzione_antenati(nome_figlio)
{
//trova nome del genitore relativo al figlio
nome_genitore = nome_figlio->genitore;
//richiama ricorsivamente la funzione
funzione_antenati(nome_genitore)
}

alla prima iterazione troverai il padre, alla seconda il nonno, alla terza il bisnonno ecc...

[Manbearpig]

http://it.wikipedia.org/wiki/Ricorsione

[Hall999]

Il problema è che vedendo esercizi già svolti capisco benissimo il suo funzionamento, la mia difficoltà è quando la devo implementare in un esercizio e non ci riesco, ecco un esempio:

Scrivere una funzione ricorsiva che dato un array A di n numeri interi ed un numero intero x restituisce il numero di elementi di A che sono maggiori di x. Ad esempio se A vale (1,6,3,7,8) e x=5 la funzione deve restituire 3, perchè ci sono 3 elementi maggiori di 5.
Scrivere quindi il main che richiama la funzione leggendone gli argomenti da tastiera (o impostandoli da programma) e visualizzandone i risultati sullo schermo.

[cionci]

Io per la ricorsione ho sempre ragionato in modo molto simile alle dimostrazioni per induzione.

Prima di tutto scrivo la condizione di arresto: cioè quando la mia funzione deve terminare la ricorsione.

Ad esempio nel caso in cui i dati su cui si lavorano è un vettore, la condizione di arresto è quando sono arrivato all'ultimo elemento del vettore o non ci sono elementi su cui lavorare.

Poi scrivo la condizione di funzionamento generica, cioè mi dimentico di tutto quello che c'è d'interno e mi metto in un caso di funzionamento in cui ho ha disposizione dati e devo lavorare su un generico elemento.

Ragionando sempre su un vettore, mi riferisco al caso in cui sia nel mezzo al vettore.

Semplicemente scrivo cosa dovrei fare con quel dato elemento e metto in relazione l'elemento con i risultati che mi ritorna la ricorsione (o le ricorsioni). Senza pensare alle condizioni limite, ma solo al funzionamento a regime, al resto ci pensa la condizione di arresto.

Generalmente isolando i due problemi le cose vengono molto naturali e permettono di risolvere esercizi sulle ricorsioni in maniera molto "naturale".