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

Ciao a tutti.
Cercavo qualche volenteroso e coraggioso in grado di farmi esempi di
ricorsioni ben commentati, soprattutto nel caso di liste, alberi
binari, ed altre strutture che utilizzano i record.
Grazie.
Cordiali saluti.
Matteo.

 wrote in message 38077af...@news.tin.it...

Ciao caro Matteo,
vedo che nessuno ti ha ancora risposto e così provo a parlarti io della
ricorsione.
La ricorsione è un modo molto 'elengante' di progettare algoritmi, o, come
diceva il mio prof., è un modo per elevare il livelo di astrazione...
Se conosci un po' di matematica, forse non ti sarà estraneo il concetto di
'induzione matematica'.
Il principio di Induzione vale per qualsiasi struttura 'ordinata', ossia che
si può mettere in corrispondenza con l'insieme dei Numeri Naturali.
Senza entrare molto nel dettaglio, vedila così:
Per dimostrare che una proprietà P vale per tutti i numeri naturali si
dimostra che:
    1.    P vale per 0    (passo base)
    2.    se P vale per un naturale n allora vale anche per n+1  (o succ(n))
(passo induttivo).
Esempio:
Prendiamo x e y naturali e definiamo la funzione 'somma' in questo modo:
                        /    x     , per  y=0    (passo base)
somma(x,y) =  |
                        \    succ(somma(x,pred(y)))     , per y>0
(passo induttivo)
Da questa semplice definizione, che non è altro che la somma di due numeri
naturali come tutti la conoscono, scriviamo il codice Pascal
#####################################
PROGRAM SommaRicorsiva(output);
Function somma(x,y:integer):integer;
Begin
   if (y=0) then somma:=x
                else somma:=somma(x,y-1)+1
End;
BEGIN
   write(somma(5,3));
END.
#####################################
Proviamo a simulare la funzione:
somma(5,3) = somma(5,2)  +  1      =  7 + 1 = 8
                               ||
                               v
                       somma(5,1)  +  1      =  6 + 1 = 7
                               ||
                               v
                       somma(5,0)  +  1      =  5 + 1 = 6
ed ora il codice con le chiamata ricorsive:
(per il 'grafico', prima scendi aprendo i rda della ricorsione e poi risali
dall'ultimo rda con i return)    (scusa, ma disegno da schifo...)
Record Di Attivazione                     Risultato
 _____main______
|                              |  --------------->  stampa   8
|_______________|    <---,
              | |                          |
              v                          |            ritorna    7  + 1 = 8
 ____somma_____            |   [else somma:=somma(x,y-1)+1]
|    x = 5                  |  ------/
|_____y_=_3_____|    <---,
              | |                          |
              v                          |            ritorna    6  + 1 = 7
 ____somma_____            |   [else somma:=somma(x,y-1)+1]
|    x = 5                  |  ------/
|_____y_=_2_____|    <---,
              | |                          |
              v                          |            ritorna    5  + 1 = 6
 ____somma_____            |   [else somma:=somma(x,y-1)+1]
|    x = 5                  |  ------/
|_____y_=_1_____|    <---,
              | |                          |
              v                          |            ritorna    5
 ____somma_____            |       [if (y=0) then somma:=x]
|    x = 5                  |  ------/
|_____y_=_0_____|
E' a questo punto che si ferma la ricorsione e incominciano i 'ritorni'
(scusa il linguaggio strano...)
Il bello (ma anche, talvolta, difficile da gestire) è che ogni chiamata
ricorsiva apre un nuovo rda con le sue variabili locali (per capirci x e y
non vengono 'sovrascritte', ma ad ogni ricorsione sono variabili 'nuove').
Puoi fare ricorsivamente anche la moltiplicazione, l'esponenziale, ecc.
Sono svariate le funzioni che puoi realizzare xon la ricorsione, e molte
senza la ricorsione sarebbero dei veri rompicapo:
calcola la profondità di un albero binario
##########################
TYPE TipoElemAlbBin=...;      {   per es. integer   }
           TipoAlbBin=^TipoRecAlbBin;
           TipoRecAlbBin=record info:TipoElemAlbBin;
                                                  sin, des:TipoAlbBin
end;
Function massimo(x,y:integer):integer;
Begin
    if (x>y) then massimo:=x
                 else massimo:=y
End;
Function profondita(A:TipoAlbero):integer;
Begin
    if (A=NIL) then profondita:=-1    {  per indicare l'albero vuoto  }
    else profondita:=massimo(profondita(A^.sin),profondita(A^.des))
End;
############################
Riflettici: è moooolto bella! E ce ne sono molto più belle!
P.S.: Ricorda che ogni chiamata ricorsiva ti porta via un po' di memoria,
quindi non esagerare: io non farei mai la distruzione totale o costruzione
di una lista di record e puntatori ricorsivamente... anche se è più bello.
P.P.S.: Scusa se trovi errori nel codice ma ormai programmo solo in C++ da
più di un anno...
--
Ciao da Pavelo, e che lo sforzo sia con te!
E-mail: 
pi....@bigfoot.com
        (se 'rispondi al mittente', togli NO_SPAM)
HomePage: 
http://web.tiscalinet.it/pavelo
ICQ UIN #37941259
Fortunatamente, secondo la moderna astronomia,
l'universo e' finito: un pensiero consolante per chi,
come me, non si ricorda mai dove ha lasciato le cose.
    Woody Allen