Ricorsione

• Almeno una delle alternative deve contenere un'istruzione ricorsiva al metodo; questa dovrà

contenere argomenti più "piccoli" o versioni ridotte dell'algoritmo (nel senso che essa dovrà essere

frutto di un controllo, e quindi analizzare solo determinati casi);

• caso di base arresto,

Almeno un'alternativa deve essere un o di ovvero un caso nel quale il metodo

esegue il compito previsto senza alcuna chiamata ricorsiva.

I casi base nascono per terminare ogni possibile sequenza di chiamate ricorsive; infatti, se una chiamata di un

metodo causa una ricorsione allo stesso metodo, essa può causare un'ulteriore ricorsione allo stesso metodo e

così via. Se non esistesse un'istruzione in cui il metodo assume di non dover applicare alcuna ricorsione, esso

ricorsione infinita.

non terminerebbe tutti gli altri casi attivi e si incorrerebbe in una

Un tipico metodo è il blocco if­else, in cui si applica un metodo ricorsivo se viene rispettata la condizione,

altrimenti si ritorna qualcos'altro e si termina il ciclo di ricorsioni.

Lo stack e la ricorsione

Le chiamate ricorsive sono chiamate a metodi; quindi, l'invocazione di un metodo comporta la creazione di

un nuovo record di attivazione e il suo posizionamento in cima allo stack. I parametri formali del nuovo

metodo vengono inizializzati, con gli argomenti passati in ingresso al momento della chiamata ricorsiva.

Quando incontra la chiamata ricorsiva, il computer interrompe l'esecuzione in corso su quel record di

attivazione e passa a eseguire le istruzioni sul nuovo record, per trovare il risultato relativo alla chiamata

ricorsiva.

Se arriva una nuova chiamata ricorsiva viene chiamato un n­esimo record in cima allo stack e il computer

interrompe anche questa chiamata per trovare la soluzione a quella che è ora in cima allo stack.

Al termine il computer elimina il record di attivazione, e l'elaborazione sospesa sotto di esso riprende.

overflow

N.B.: si definisce il limite dello stack: quando si verifica una lunga serie di chiamate ricorsive di un

metodo, ogni chiamata produrrà il salvataggio di un'elaborazione sospesa sullo stack, ma questo ha un limite.

Quindi se una sequenza è troppo lunga, lo stack cercherà di estendersi oltre i limiti restituendo un risultato di

overflow.

N.B.: generalmente è preferibile usare un metodo iterativo piuttosto che uno ricorsivo, in quanto quest'ultimo

è spesso più oneroso, andando a creare ogni volta un nuovo record di attivazione in cima allo stack.

N.B.: un metodo ricorsivo può essere un metodo void o può restituire un valore.

Programmare utilizzando la ricorsione

Quando si definiscono e si utilizzano i metodi ricorsivi, non si vogliono tenere presenti la gestione dello

stack e le esecuzioni sospese; un privilegio della ricorsione è quello di poter ignorare questi dettagli.

Tutto ciò che è necessario fare quando si programma con metodi ricorsivi, è assicurarsi che siano soddisfatte

le seguenti tre proprietà: ricorsione infinita;

Non si deve verificare

1. caso di arresto

Ogni deve restituire il valore corretto per quel caso;

2. Per i casi che coinvolgono la ricorsione, se tutte le chiamate ricorsive restituiscono il valore corretto,

3. valore finale

allora il restituito dal metodo è quello corretto.

N.B.: le stesse regole possono essere applicate anche in un metodo ricorsivo void:

ricorsione infinita;

Non si deve verificare

1.