Fig 1
Nel settore informatico il processo ricorsivo si applica a diversi tipi di dati. Ad esempio, per aumentare il contrasto di una immagine si passa la figura una prima volta. Quindi si ripete il trattamento finché il contrasto non raggiunge la qualità desiderata.
Molto più noto è il processo ricorsivo che calcola una funzione matematica, a cui lei probabilmente si riferisce. Si cominciò a studiare il metodo negli anni 20 da parte di logici come Hilbert, Skolen, ecc. Godel nel 1931, sfruttando una proposta di J. Herbrand, formulò il concetto generale di funzione ricorsiva. Il rumore nato intorno alla ricorsione è in parte dovuto al nesso che A.M. Turing e A. Church stabilirono in rapporto alla decidibilità di un calcolo. La ricorsione è anche connessa al metodo induttivo di dimostrazione di un teorema.
Come si programma una funzione ricorsiva?
Alcuni linguaggi, come il Prolog ed il Lisp, permettono la scrittura diretta degli estremi logico-matematici della funzione ricorsiva. Cioè il programmatore definisce le condizioni iniziali della funzione e la regola di ricorsione, poi ci pensa il compilatore a sviluppare l'algoritmo ricorsivo. Come esempio prendiamo la funzione fattoriale che è pari a:
N!= N*(N-1)*(N-2)*(N-3)...3*2*1
la condizioni iniziale stabilisce che il fattoriale di zero sia uno. La regola, facilmente ricavabile dalla formula sopra scritta, pone che il fattoriale del generico N sia pari al fattoriale (N-1)! moltiplicato per N. Quindi il programmatore scrive:
0! = 1
N! = (N-1)! * N
Quando il programmatore usa un linguaggio comune invece del Prolog e del Lisp, deve sviluppare appositamente il ciclo la cui logica compare in Figura 1. Ad esempio, il programma comincia a calcolare il fattoriale di 1, riprende l'output F finché il risultato non è esatto cioè non produce il valore F=N! richiesto. Il programmatore scrive un algoritmo del genere:
Leggi N
X = 1
F = 1
Ripeti finché X=N
F=X*F
X=X+1
Fine- Ripeti
Stampa F
Il valore iniziale del ciclo viene chiamato seme (nell'esempio è F=1).
Lei mi domanda quali sono i problemi della tecnica ricorsiva.
Il principale riguarda i suoi limiti: non tutte le funzioni possono essere
calcolate in questo modo.
Come contropartita c'è il vantaggio che le principali funzioni ricorsive sono
pubblicate e sono consultabili da parte degli addetti ai lavori.
Nonostante l'enfasi sulla ricorsività, devo aggiungere che tali questioni non toccano molto l'informatico nei comuni ambienti di lavoro che sono le banche, le aziende, i commerci ecc. Di regola il programmatore traduce le specifiche che gli vengono fornite (v. risposta 38) ed usa il calcolo ricorsivo se gli viene richiesto esplicitamente e se l'algoritmo di ricosione è disponibile, altrimenti non se lo inventerà. A meno che non lavori in un centro apposito dedicato ad applicazioni avanzate normalmente il tecnico non si avventura nelle problematiche della ricorsione.
Questi
aspetti professionali vanno sottolineati, perché alcuni
docenti
specie universitari, invece
di porre e di risolvere i problemi che si presentano nella vita reale,
si dilungano in tematiche molto particolari. In questo modo allontanano lo studente dal mondo del lavoro e, quel che è peggio, gli riempono la testa di
astrusità.
anno 2005