La ricorsione (detta anche recursione o ricorrenza) è un metodo comune a tutti i sistemi produttivi. Consiste nel generare un prodotto secondo un processo e di risottoporlo a tale processo finché l'output non raggiunga il livello di qualità voluto. Ad esempio l'alcool si ottiene dalla distillazione delle vinacce. Si ricava un liquido che viene sottoposto più volte dallo stesso processo di distillazione finché la concentrazione di alcool non arriva al 99,99%. La logica di tale procedimento viene illustrata dal seguente diagramma.

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

104. Le chiedo ancora:quali possono essere i problemi nell'implementazione ricorsiva di un algoritmo?

105.Quali sono le caratteristiche delle interfacce grafiche?

Ho spiegato che le euristiche di Nielsen danno una indicazione (v. risposta 101) succinta ed anche un pò semplicistica perché le interfacce grafiche appartengono al grande tema della comunicazione umana che dipende da tanti fattori i quali talora mostrano caratteristiche opposte e contrarie. Ad esempio la comunicazione esprime contenuti freddi e razionali, ed anche elementi suggestivi ed irrazionali. Segue dinamiche psicologiche e muta al volger delle mode. La materia è così ampia ed articolata che non si può qui affrontare; men che meno ridurre ad una sintesi. 

Oggi i committenti chiedono prodotti multimediali tanto efficaci che soltanto i creativi, gli artisti ed i pubblicitari sono all'altezza. Al tecnico informatico non resta che documentarsi e capire la natura della comunicazione. Per questa ragione, nelle mie lezioni introduco uno schemino, il quale non fornisce soluzioni, ma tende a maturare le menti.

L'utente al computer



PS: Alla sua ultima domanda risponderò in privato.

 

 

 

anno 2005