6 . Metodologia top-down e sottoprogrammi Versione 5.0 – Aprile 2023
Esempi di problemi con la ricorsione
( A ) Secondo la matematica la definizione ricorsiva della somma dei primi n numeri interi strettamente positivi può essere formalizzata nel seguente modo :
Somma ( n ) = 1 se n = 1 Somma ( n ) = n + Somma ( n-1 ) se n > 1
Possiamo quindi scrivere il seguente pseudocodice della funzione ricorsiva Somma FUNZIONE Somma ( VAL n : INT ) : INT s : INT
RITORNA ( s ) FINE
Dettagliamo la seguente chiamata ricorsiva
…. s � Somma ( 5 )
…..
Il valore del parametro attuale ( costante intera ) trasferito al parametro formale n è 5 .
Attivata la funzione viene eseguita l ’ istruzione s� 5 + Somma ( 4 ) che non può essere eseguita e risolta direttamente in quanto contiene una chiamata allo stesso sottoprogramma ( procedura ricorsiva diretta ) che conduce alla seguente successione
s� 5 + ( 4 + Somma ( 3 )) s� 5 + ( 4 +( 3 + Somma ( 2 ))) s� 5 + ( 4 +( 3 + ( 2 + Somma ( 1 )))) s� 5 + ( 4 +( 3 + ( 2 + ( 1 )))) che è uguale a 15
Clausola di terminazione
Il valore di n si semplifica
Ricorsione infinita : i valori del parametro non si semplificano FUNZIONE Somma ( VAL n : INT ) : INT s : INT
Clausola di terminazione
Il valore di n NON si semplifica
Pag . 30