Newsgroup: it.comp.lang.pascal
Titolo: Ricorsione

Ciao a tutti! Mi pare di capire che siete tutti molto preparati
sull'argomento quindi sono capitato nel posto giusto! Pregherei chiunque
di darmi una mano...avrei bisogno che qualcuno mi spiegasse in parole
molto semplici (davvero molto!) cos'è la ricorsione. Dovrei portare un
esempio matematico ed uno informatico (tipo con Visual Basic)...che
faccio?? Vi ringrazio anticipatamente...
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 
La ricorsione è la caratteristica di tutti quei procedimenti che per 
essere completati richiamano se stessi diminuendo tutte le volte il 
proprio campo di applicazione.
E' possibile risolvere un problema in maniera ricorsiva applicando il 
cosiddetto principio del DIVIDE ET IMPERA, ovvero, laddove sia possibile 
scomporre il problema principale in tanti sottoproblemi più piccoli *ma 
di natura analoga*, il risultato è un insieme finito di istruzioni che 
si auto richiama per concludere il computo.
Un esempio pratico potrebbe essere quello della pila di piatti da 
lavare. Immagina di avere tanti piatti tutti uno sopra l'altro sul 
lavabo della cucina. La procedura che lava tutti i piatti della pila è:
Data la pila:
- Se la pila è vuota abbiamo finito
altrimenti:
- Leva un piatto dalla pila
- Lava il piatto
- Lava i piatti della pila rimasta
dove nell'ultima istruzione intendiamo che levando un piatto dalla pila 
è rimasta una pila più piccola ma che ha le medesime caratteristiche di 
quella di partenza, pertanto alla fine richiamiamo lo stesso 
procedimento, che verrà eseguito ogni volta (ogni istanza) sulla pila 
più piccola.
a un certo e determinato momento la pila si esaurirà e all'istanza 
successiva la pila risulterà vuota. Questo sarà la naturale terminazione 
del nostro computo poiché non verranno più aperte istanze e tutte le 
altre termineranno progressivamente.
In questo caso risulta peraltro abbastanza semplice ed immediato il 
confronto con la versione iterativa del problema che viene senz'altro 
più immediata:
  finché la pila NON è vuota
    leva un piatto dalla pila
    lava il piatto
  ripeti
Un esempio matematico molto semplice è quello dell'elevamento a potenza:
  se definisci X alla N (X base, N esponente) come il prodotto tra X e X 
alla N-1 ottieni quanto segue (notazione informatica)
  X^N  = X   *    X^(N-1)
ovvero la risoluzione di X^N si può risolvere tramite un prodotto tra X 
(che è un dato iniziale) e una potenza che è appunto il medesimo 
problema di partenza, anche se abbiamo diminuito l'esponente di 1.
Quando ci fermiamo?
Quando abbiamo raggiunto 0 come esponente perché sappiamo che il 
risultato sarà sempre e comunque 1 a prescindere dal valore di X.
Ti codifico in Pascal il sottoprogramma ricorsivo (in altro linguaggio 
sarei off topic)
Function potenza(base:real; esponente:integer):real;
Begin
   If esponente=0 then potenza:=1
                  else potenza:=base*potenza(base,esponente-1)
end;
abbiamo così definito una funzione che accetta in ingrasso i due 
parametri, la base (in virgola mobile) l'esponente (intero).
Escludiamo l'esponente negativo che va a complicare leggermente il 
procedimento, in ogni caso puoi vedere come la scrittura della funzione 
in maniera ricorsiva sia vicina alla formula che ho scritto sopra, che è 
poi l'unico vantaggio che ha la ricorsione.