Newsgroup: it.comp.programmare
Titolo: ricorsione

Ciao.
Potreste spiegarmi cos'e' la ricorsione e come
si applica nei linguaggi orientati agli oggetti e in quelli
procedurali?



La ricorsione, detta in termini poverissimi, e' la capacita' da parte delle
funzioni, di svolgere determinati compiti, richiamando se stesse.
Non c'e' una sostanziale differenza tra linguaggi oo e linguaggi
procedurali, da questo punto di vista, in quanto i linguaggi oo generalmente
posseggono il concetto di "funzione" e quindi *possono* implementare la
ricorsione.
Un esempio simpatico di funzione ricorsiva e', per esempio, quello che
scrive la trasformazione binaria di un numero, in C:
#include <stdio.h>
/* funzione ricorsiva */
void write_binary_digits(int x)
{
     if (x > 0)
     {
        write_binary_digits(x >> 1);
        printf("%c", "01"[x & 1]);
     }
}
void binary_form(int x)
{
     if (x == 0)
       printf("0");
     else
       write_binary_digits(x);
     printf("\n");
}
int main()
{
    binary_form(6);
    return 0;
}
--------------------------------
Inviato via 
http://usenet.libero.it

 }
[cut]
Potresti scrivermi e descrivermi in linguaggio
naturale un algoritmo in cui viene usata una
funzione ricorsiva?
Ti faccio questa domanda perche' sono
non conosco il C. Finora ho visto solo
un po' di Visual Basic 6.

 ha scritto:
[cut]
Potresti scrivere e descrivere *in linguaggio
naturale* un algoritmo in cui viene usata una
funzione ricorsiva?
Ti faccio questa domanda perche'


 un po' di Visual Basic 6.
Scusa se mi intrometto, ma vorrei fare una prova:
Trascrivo l'algoritmo di Andrea Laforgia in questo modo:
===============
#funzione ricorsiva
def write_binary_digits(x):
    if (x>0):
        write_binary_digits(x/2)
        print x%2
def binary_form(x):
    if x is not 0:
        write_binary_digits(x)
    elif x is 0:
        print 0
binary_form(6)
===============
Ci diresti se ti è più comprensibile dell'altra versione?
Poi, in ogni caso, ti spiego come funziona, ok?
Ciao!
--
Gerolamo

 procedurali?
La ricorsione è la possibilità data alle subroutines di chiamare se stesse:
Esempio:
Mettiamo per esempio che debba fare la potenza di un numero con esponente
intero positivo:
Funzione Potenza(Numero, Esponente)
  If Esponente=0 Risultato=1
   Altimenti  Risultato=Numero * Potenza(Numero,Esponente-1)
 Fine Funzione
Si può notare come La funzione chiama se stessa, in memoria si avrà la
creazione di una pila con allocazione di memoria per ogni chiamata.
Esempio se Esponente = 5
In Memoria si avrà questa cosa:
  Chiamata Potenza[1] (Allocazione)
    -  Chiamata Potenza[2] (Allocazione)
     --  Chiamata Potenza[3] (Allocazione)
      ---  Chiamata Potenza[4] (Allocazione)
       ---- Chiamata Potenza[5] (Allocazione)
       ---- (Disallocazione) Chiamata Potenza[5]
      ---  (Disallocazione) Chiamata Potenza[4]
     -- (Disallocazione) Chiamata Potenza[3]
    - (Disallocazione) Chiamata Potenza[2]
   (Disallocazione) Chiamata Potenza[1]
Prova Questa funzione:
function crash(const int a){
  if (a = = (a-1)) return a;
   else return crash(a);
}
Sicuramente il compilatore ti darà uno Warning su (a = = (a-1)), te compila
lo stesso, capirai cosa succede quando si usa la ricorsione.
Per la programmazione OOP, ci sono delle cose da sapere, in alcuni casi non
può essere usata, allora si aggira l'ostacolo facendo richiamare una
funzione ricorsiva di appoggio esterna all'oggetto che necessità di
utilizzare la ricorsione.
Esempio se c'è il metodo "pippo" che deve usare la ricorsione si crea
un'altra funzione "pippo2" ricorsiva e pippo chiama semplicemente "pippo2"

 }
Qua ad esempio la funzione non restituirà mai un risultato finito, perchè  a
sarà sempre diversa da a-1 e quindi la funzione chiamerà se stessa fino a
saturare la memoria dello STACK e a mandare in crash l'applicazione che ne
fa uso.

 ha scritto nel messaggio
news:%a9s9.8911$TD1.3...@news2.tin.it...

Grazie delle spiegazioni.
Da qualche parte ho letto che la ricorsione rallenta
un algoritmo. E' vero?

 Trascrivo l'algoritmo di Andrea Laforgia in questo modo:
[cut]
La spiegazione di Giovanni Caglia credo che sia stata
per me piu' chiara. Grazie lo stesso.

 ha scritto nel messaggio
news:f09s9.8857$TD1.3...@news2.tin.it...

[cut]
Pensandoci bene, non mi sono chiari i passaggi.
Nella prima chiamata ad es di Potenza(2,5),
facendo tutti i passaggi -che sono poi dei cicli-,
il risultato e' 1.
Non mi e' chiaro cosa viene allocato in memoria.
Sarebbe meglio se mi indicassi tutte le operazioni
svolte passaggio per passaggio.

 un algoritmo. E' vero?
Non rallenta un algoritmo, forse l'esecuzione dello stesso per via delle
continue chiamate a funzione.
Si parla cmq di quantità assolutamente minimali e spesso trascurabili.
Saluti,
-- 
         (__)	      | Nicholas Wieland	    |    -     ------------
	 (oo)	      | 
nicholas...@yahoo.it
   |    -    | There's no |
   /------\/ 	      | Debian GNU/Linux / Mac OS X |    -    | place like |
  / |    ||  	       -----------------------------     -    | *GNOME(2)* |
 *  /\---/\           ...."Have you mooed today?"....    -     ------------

 facendo tutti i passaggi -che sono poi dei cicli
E' qui che sbagli, non sono dei cicli, non li devi vedere come dei cicli.
Devi vedere la chiamata come la chiamata ad una differente funzione, anches
se ha lo stesso nome.

 Si parla cmq di quantità assolutamente minimali e spesso trascurabili.
E' vero, non lo rallenta, però se si trova un algoritmo iterativo che ha lo
stesso costo computazionale di quello ricorsivo, è preferibile scegliere il
primo.
Nota che ho scritto "algoritmo" iterativo e non implementazione iterativa
(sono capaci tutti a trasformare un algo. ricorsivo in iterativo utilizzando
uno stack esplicito...l'algoritmo resta sempre ricorsivo, sebbene la sua
implementazione sia iterativa).
Kiuhnm