[java] ricorsione

[fabdort]

Buon giorno a tutti. Ancora non mi é chiaro il concetto di ricorsione, e guardando tra le varie guide e tutorial che ho trovato in internet, non sono riuscito a trovare informazioni per chiarirmi in concetto. C´é qualche anima pia disposta ad aiutarmi a capire come funzia, le caratteristiche e quando é conveniente usare la ricorsione???
Grazie mille per l´attenzione

[Xadoom]

La ricorsione consiste nel creare una funzione che dato un problema compie le seguenti operazioni:
1)Confronta il problema con un caso semplice che sa risolvere
2)Se lo sa risolvere ritorna il risultato, altrimenti chiama "se stessa" passandosi un problema più piccolo.

Detto così è incasinato, vediamo un esempio:
Problema: dato un intero n calcolare n! (1x2x3x4x...xn)
Per risolverlo con la ricorsione si crea una funzione del tipo:

int fattoriale(int n){
  /*Se n è 1 il suo fattoriale è 1*/
  if(n==1) return 1;
  /*Se n è diverso da 1 allora utilizzo la propietà che
    n! = n * (n-1)!
    e richiamo la stessa funzione con un "problema più piccolo
  */
  else return n*fattoriale(n-1);
}

I problemi che si risolvono con la ricorsione si possono risolvere anche con metodi iterativi, ma può risultare meno elegante:
Comunque che io sappia le applicazioni sono tutte puramente di tipo matematico; personalmente io non la ho mai utilizzata (a parte le solite applicazioni matematiche appunto).
Bah spero di non averti confuso ulteriormente, comunque cerca sul forum se ne è parlato spesso!

[fabdort]

Grazie per la risposta. Ho giá cercato sul forum, ma con scarsi risultati (nel senso che non avevo capito molto).
Comunque se nono erro funzia cosí (correggimi se sbaglio)
Il caso semplice é quello in cui n = 0 percui posso assegnare il valore 1. Nel caso in cui n>0 nn posso risolvere la funzione, perché con l´espressione n*fattoriale (n-1) richiamo ancora il metodo fattoriale (int n) (con n = n-1), al quale non posso assegnare alcun valore (inizializzo la variabile solo nel caso n=0), percui "scendo" fino a quando non arrivo a n=0 a cui posso assegnare un valore definito (in questo caso 1) per poi "risalire".
Spiegazione semplice no??? :master:

[anx721]

Comunque che io sappia le applicazioni sono tutte puramente di tipo matematico; personalmente io non la ho mai utilizzata (a parte le solite applicazioni matematiche appunto).

Bhè, la ricorsione è usata anche in tanti altri ambiti, ad esempio in algoritmo su alberi o per l'ordinamento.

[Xadoom]

Originariamente inviato da fabdort
Grazie per la risposta. Ho giá cercato sul forum, ma con scarsi risultati (nel senso che non avevo capito molto).
Comunque se nono erro funzia cosí (correggimi se sbaglio)
Il caso semplice é quello in cui n = 0 percui posso assegnare il valore 1. Nel caso in cui n>0 nn posso risolvere la funzione, perché con l´espressione n*fattoriale (n-1) richiamo ancora il metodo fattoriale (int n) (con n = n-1), al quale non posso assegnare alcun valore (inizializzo la variabile solo nel caso n=0), percui "scendo" fino a quando non arrivo a n=0 a cui posso assegnare un valore definito (in questo caso 1) per poi "risalire".
Spiegazione semplice no??? :master:

Esatto, ma nel caso della ricorsione devi fermarti per n=1 in cui il fattoriale vale 1. 0! non credo sia contemplato.
Ultimamente in un post si parlava del calcolo di un esponenziale EXP[n] e di come implementarlo, è del tutto analogo, ma in quel caso ti devi fermare a n=0 in quanto EXP[0]=1.
Effettivamente per altre applicazioni oltre a quelle matematiche non sono ferrato, magari qualcun'altro saprà risponderti meglio.
Ciao

[LeleFT]

Originariamente inviato da Xadoom
Esatto, ma nel caso della ricorsione devi fermarti per n=1 in cui il fattoriale vale 1. 0! non credo sia contemplato.

Ehm... 0! = 1 per definizione!


Ciao.

[fabdort]

Ok per adesso mi basta cosi. Ho appena iniziato con la programmazione, ed anche se vedessi esempi complessi non riuscirei comunque a capirli, anzi probabilmente mi farebbero solo confusione. Sarebbe stato interessante vedere quando si applica e quando no, ma comunque credo che al momento giusto risolveró anche questo problema. Grazie mille per la spiegazione.

[Xadoom]

Originariamente inviato da LeleFT
Ehm... 0! = 1 per definizione!


Ciao.

Immaginavo, comunque non ha molto senso.... :tongue:

[LeleFT]

Originariamente inviato da Xadoom
Immaginavo, comunque non ha molto senso.... :tongue:

Effettivamente 0! = 1 non sembra avere molto senso, però si può dimostrare in due modi che 0! è proprio 1:

1) Dato che il fattoriale di n è uguale, per definizione, a n * (n - 1)!, allora 1! = 1 * 0!. Ma, dato che 1! = 1 ==> 0! = 1.

2) Dato che il fattoriale di n indica il numero di tutte le possibili permutazioni di un insieme di n elementi, senza ripetizioni, allora 0! indica il numero di permutazioni possibili in un insieme costituito da 0 elementi. Un insieme costituito da 0 elementi ha una ed una sola permutazione possibile ==> 0! = 1.


Ciao.