ricorsione

ricorsione

Metodo per definire funzioni in modo tale che la funzione includa sé stessa nella propria definizione. Si tratta di una tecnica di programmazione molto potente e molto sfruttata in informatica, in quanto consente di suddividere il problema da risolvere in sottoproblemi analoghi all’originale ma più semplici, perché agenti su dati di ingresso ridotti. Un algoritmo ricorsivo è definito in due fasi: dapprima si definisce la risoluzione di un problema simile a quello di partenza ma di dimensione ridotta (passo base); quindi si definisce il passo di risoluzione generale come combinazione di problemi di dimensione inferiore. Si ha ricorsione diretta quando una procedura o funzione richiama direttamente sé stessa all’interno della propria definizione. Si parla invece di ricorsione indiretta quando nella definizione compare la chiamata ad altra procedura o funzione che direttamente o indirettamente richiama la procedura o funzione di partenza. La chiamata ricorsiva termina al verificarsi di una condizione particolare, detta di uscita o di terminazione. Spesso un programma ricorsivo può essere riscritto in forma iterativa, mediante una semplice struttura di controllo condizionale. Il tipico esempio è la funzione matematica fattoriale, definita per ogni intero positivo n e denotata n!. La sua possibile definizione ricorsiva (diretta) è: 1!=1 (passo base); n!=n∙(n−1)!. Malgrado la potenzialità di decomposizione di problemi complessi, la tecnica della ricorsione presenta anche alcune insidie di programmazione. Un primo rischio è la ricorsione infinita, che si presenta quando è assente la clausola di chiusura della chiamata. Un’ulteriore insidia è quella dell’inefficienza di memoria (overhead), in quanto possono essere allocate variabili locali non necessarie. Infine, alcuni problemi possono richiedere soluzioni ricorsive di complessità non lineare, che può portare rapidamente a una saturazione delle risorse. La sua eleganza e sinteticità tuttavia ne consigliano l’uso in una vasta serie di applicazioni, come la valutazione di funzioni matematiche, la gestione di dati strutturati ad albero, la creazione di oggetti frattali, gli algoritmi di ordinamento.

→ Informatica teorica; Programmazione, linguaggi di