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ù famoso è il processo ricorsivo che calcola una funzione matematica, a cui lei probabilmente si riferisce. Si cominciò a studiarlo 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
Per cui 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 usano i linguaggi comuni, il programmatore deve sviluppare appositamente il ciclo 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.
Le principali funzioni ricorsive sono state scoperte e sono rese note agli addetti. Altre saranno definite in futuro, immagino.
Nonostante l'enfasi sulla ricorsività, devo aggiungere che tali questioni toccano l'informatico di lato nei comuni ambienti di lavoro: banche, aziende, commerci ecc. Infatti (v. risposta 38) i compiti dei due principali professionisti sono i seguenti:
- L'analista prepara le specifiche tecniche sulla base delle richieste del committente,
- Il programmatore traduce le specifiche nel programma finale.
Questo ultimo userà un calcolo ricorsivo se viene chiesto e se l'algoritmo di ricosione è disponibile, altrimenti non se lo inventerà. A meno che non lavori in un centro di ricerca apposito dedicato a questo tipo di problemi.
Questi
aspetti professionali vanno ben sottolineati, perché alcuni professori (universitari), invece
di porre i problemi che si presentano nella nostra professione ed invece di
insegnare a risolverli,
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à.