3° Anno TEORIA 7. Metodologie di progettazione e programmazione | Page 22

6 . Metodologia top-down e sottoprogrammi Versione 5.0 – Aprile 2023

LA RICORSIONE

Abbiamo visto che nel corpo di un sottoprogramma è possibile chiamare ( attivare ) altri sottoprogrammi dichiarati esternamente o localmente ad esso , ma è anche possibile , in determinate condizioni , fornire l ’ istruzione per chiamare ( riattivare ) se stesso .
In questo caso si parla di sottoprogrammi ricorsivi , una caratteristica prevista da alcuni linguaggi di programmazione ( ad esempio per il C è prevista ).
DEF : In generale si definisce ricorsività o ricorsione la possibilità di definire un problema riferendosi ( ossia ricorrendo ) alla sua stessa definizione .
Per potere attivare un processo risolutivo di tipo ricorsivo occorre rispettare i seguenti tre requisiti :
1 . il problema principale ( caso generale ) può essere scomposto in sottoproblemi dello stesso tipo , ognuno dipendente dall ’ altro in base ad una scala gerarchica ( ossia con ordine di complessità inferiore );
2 . è necessario conoscere la soluzione di un caso particolare del problema principale ; ciò è indispensabile per poter arrestare la ricorsione ( condizione di terminazione della ricorsione );
3 . devono essere note le relazioni funzionali che legano il problema principale ( caso generale ) ai sottoproblemi simili
DEF 1 : Un sottoprogramma implementa la ricorsione DIRETTA quando nella sua definizione compare UNA SOLA CHIAMATA al sottoprogramma stesso .
Primo esempio : POTENZA N-ESIMA DI UN NUMERO
In matematica sono possibili due definizioni generali di potenza n-sima di un numero a intero non nullo elevato ad un esponente n intero non negativo .
- definizione non ricorsiva a n = 1 se n = 0 e a ≠ 0 a n = a * a * ……… * a se n > 0 n volte
- definizione ricorsiva a n = 1 se n = 0 e a ≠ 0 a n = a * a ( n-1 ) se n > 0
Questo problema è stato espresso in termini ricorsivi , in quanto risponde ai tre requisiti enunciati poco fa . Infatti :
1 . sappiamo che calcolare a n dipende esclusivamente dal calcolo di a ( n-1 ) ( scala gerarchica ); 2 . conosciamo la soluzione del caso particolare che a 0 = 1 ( condizione di terminazione );
3 . abbiamo una relazione funzionale a n = a * a ( n-1 ) che lega il problema principale ( a n ) al sottoproblema simile ma di complessità minore ( a ( n-1 ) ).
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it )
Pag . 22