PDA

Visualizza la versione completa : c ricorsione


ciro78
20-05-2004, 16:15
int f;
if(!numero)
f=1;
else
f=numero*fattoriale(numero-1);
return f;


salve il seguente codice è parte di una funzione chiamata fattoriale
il problema è il seguente.il manuale dice che si tratta di ricorsione ma sinceramente non capisco come avvenga il calcolo.chi può aiutarmi?

grazi ein anticipo

ps il codice serve per calcolrae il fattoriale di n

LeleFT
20-05-2004, 16:20
Molto probabilmente l'intero codice appare così:


int fattoriale(int numero) {
int f;
if (!numero)
f = 1;
else
f = numero * fattoriale(numero-1);
return f;
}

La ricorsione stà nella penultima riga. L'istruzione


f = numero * fattoriale(numero-1);

se noti, effettua il calcolo richiamando se stessa. Questo per "scomporre" il problema risolvendone uno più semplice.
Il fattoriale di un numero X (X!) è definito, in analisi, come segue:

1) 0! = 1
2= X! = X * (X-1)!

Se noti, la definizione stessa è ricorsiva e viene usata pari pari nel codice usato. Se numero è uguale a 0 (if (!numero) ) assegna al risultato (f) il valore 1, altrimenti moltiplica il valore di numero per il valore restituito dalla funzione fattoriale calcolata in (numero - 1).

Se non ti è chiaro qualcos'altro chiedi pure.

Ciao. :ciauz:

ciro78
20-05-2004, 16:27
sai il problema è questo
so ke x!=x *(x-1)!

ma io nel codice leggo x * funzione(x-1)
dove funzione mi ripete tutte le istruzioni ma,x per me è sempre x non dimunisce come dovrebbe

inoltre non ricordo a cosa serva !numero nel'if


scusa sono agli inizi

anx721
20-05-2004, 16:46
Originariamente inviato da ciro78
sai il problema è questo
so ke x!=x *(x-1)!

ma io nel codice leggo x * funzione(x-1)
dove funzione mi ripete tutte le istruzioni ma,x per me è sempre x non dimunisce come dovrebbe

Diminuisce perchè tu invochi fattoriale(x - 1)


Originariamente inviato da ciro78

inoltre non ricordo a cosa serva !numero nel'if


serve a far sì che se numero vale zero ad f gli si dà comuqnue 1 perchè 0! = 1. (in c lo zero è considerato come false)

ciro78
20-05-2004, 16:51
grazie mille
sei stato utile

LeleFT
20-05-2004, 16:57
Allora andiamo più piano...
fattoriale è la funzione che calcola il fattoriale dell'argomento passato come parametro.
Quindi, quando io eseguo da un programma che ha definita tale funzione, la seguente riga di codice


valore = fattoriale(x);

nella variabile valore ottengo il fattoriale di x. fattoriale quindi è una funzione che riceve un parametro e ne calcola il fattoriale (un po' come sin(x) calcola il seno del suo argomento).
Le istruzioni che vengono eseguite, ad ogni passo, sono sempre le stesse, ma ciò che cambia è l'argomento, di volta in volta, passato.
Osserva bene il codice:


int fattoriale(int numero) {

Definisco la funzione e affermo che prende un parametro intero (numero) di cui voglio calcolare il fattoriale.


...
if (!numero) {

Se numero vale 0 (questo perchè in C/C++ lo zero è considerato FALSE, mentre qualsiasi altro valore rappresenta il TRUE) allora assegno alla variabile f il valore 1. Siamo tutti d'accordo che il fattoriale di 0 vale 1.


else
f = numero * fattoriale(numero - 1);

altrimenti (numero è diverso da 0), calcolo il suo fattoriale utilizzando proprio la definizione: alla variabile f assegno il valore di numero moltiplicato per il fattoriale di (numero - 1).
E' proprio qui che viene effettuato il decremento di numero: viene chiamata di nuovo la funzione per il calcolo, ma con un valore decrementato di 1!!
Quello che succede in memoria credo che non ti sia di interesse, in questo momento. Quello che devi sapere è che viene chiamata una copia delle funzione stessa alla quale viene passato un valore ovviamente diverso da quello originale (infatti viene decrementato di uno). Questa farà tutti i suoi conti e ritornerà il risultato voluto che verrà moltiplicato per il valore che attualmente ha la variabile numero.
La succesione di chiamate, per esempio, per il valore 2 è la seguente:


PASSO 1 (prima copia della funzione): f = 2 * fattoriale(1);
PASSO 2 (seconda copia della funzione): f = 1 * fattoriale(0);
PASSO 3 (terza copia della funzione): f = 1 (fattoriale di 0)
PASSO 4 (torno alla seconda copia restituendo 1): f = 1 * 1;
PASSO 5 (torno alla prima copia restituendo 1): f = 2 * 1;
PASSO 6: ritorno il risutlato finale: 2.

Spero di essere stato più chiaro e preciso di prima.

Ciao. :ciauz:

ciro78
20-05-2004, 21:17
si in effetti siete stati di aiiuto.il mio errore consisteva nel credere che la variabile restasse sempre la stessa invece,cambia inquanto ha memoria dle precedente.

Loading