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

INIZIO

SE ( n = 1 )

ALLORA s � 1

ALTRIMENTI s � n + Somma ( n-1 ) FINE SE

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