Newsgroup: it.comp.lang.c++
Titolo: fattoriale

Se la funzione factorial invece di ritornare (n-1) ritorna (n--) si blocca.
Se invece ritorna (--n), restituisce il fattoriale di (n-1). Perche'?
int factorial(int n)
{
 if (n==0 || n==1) return 1;
 else return (n*factorial(n-1));
}

 wrote in message
news:EHFT9.104076$Ou4.3...@twister2.libero.it...

Perche' chiamare una funzione con n-- significa dirle di fare il calcolo con
n e poi di decrementare n.
Il che vuol dire che stai chiamando infinite volte fattoriale passandole n e
poi decrementandolo inutilmente dopo.
Chiamandola invece con --n significa che prima decrementi n, che quindi
diventa n-1 e poi chiami fattoriale col risultato del decremento, per cui la
chiami con n-1.
Maurus

 
int factorial(int n)
{
  int a = 1;
  int j;
  for(j=2;j<=n;++j)
   a *= j;
  return a;
}
Vabbe' che i compilatori moderni sono molto ottimizzati ed eliminano 
molte ricorsioni facilmente e che la definizione matematica ricorsiva di 
fattoriale e' molto interessante.
Ma perche' scrivere codice manifestamente piu' complesso e lento del 
necessario ?
Purtroppo molti libri didattici riportano questa implementazione 
ricorsiva del fattoriale, forse va bene per capire che cosa sono le 
funzioni ricorsive, ma non insegnano assolutamente quando e' opportuno 
usarle.

 chiami con n-1.
se n=5 e scrivo return(n*factorial(n-1)) mi da 120 (che e' giusto), se
scrivo return(n*factorial(--n)) mi da 24! La prima "n" in questo secondo
caso non dovrebbe essere 5? E quindi alla fine dovrebbe essere moltiplicata
per tutti i restanti valori...


In questo caso non vale la regola "da sinistra a destra" come nella
matematica.
Il compilatore fa prima un decremento di n, poi applica la moltiplicazione
del nuovo n col fattoriale applicato al nuovo n, combinando il patatrac!
Dovresti andare a vedere come il compilatore ti ha tradotto quella riga del
return in assembler per chiarirti le idee.
Maurus

 return in assembler per chiarirti le idee.
Come faccio a vedere la traduzione in assembler?

 wrote in message
news:wfJT9.105042$Ou4.3...@twister2.libero.it...

Dipende dal tuo compilatore.
Di solito nelle opzioni di compilazione c'e' un flag da settare per ottenere
anche i files .asm
Dovresti guardare l'help delle opzioni di compilazione: poi riduci al minimo
il tuo programma, cosi' poi nell'assembler vedi cosa combina quella
moltiplicazione.
Maurus

 necessario ?
perche` spesso e volentieri la chiarezza del codice e` *molto* piu` 
importante della sua velocita`.
"""
L'ottimizzazione prematura e` la radice di tutti i mali
""" (D. Knuth)
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 importante della sua velocita`.
int factorial(int n)
{
  // factorial(n) corrisponde a: n*factorial(n-1) dove factorial(0) e' 1;
  int a = 1;
  int j;
  for(j=2;j<=n;++j)
   a *= j;
  return a;
}
Ho copiato il codice di Daniele e gli ho aggiunto un commento. Ecco, ora
siete contenti entrambi!
Tommy

Folgorato da brillante idea, Maurus ha scritto il 11 Jan 2003 
(news:avnm57$hmqdg$
1...@ID-125555.news.dfncis.de
): 

In piú, l'ordine di valutazione in n*factorial(--n) non è stabilito
ed ha comportamento dipendente dal compilatore.
-- 
"Non mi piace il football, sta troppo ovunque: secondo me, l'eccesso di
calcio va a discapito del fosforo." (Marc 'O Chivec)
http://www.geocities.com/fabienstein



Vorrei far notare che la funzione "fattoriale" e' definita nel solo
insieme dei numeri naturali (N) e non dell'insieme dei numeri interi
(I).
Tralasciando le controversie tra matematici sull'appartenenza, o meno,
dello zero all'insieme dei numeri naturali, qualunque funzione per il
calcolo del fattoriale non dovrebbe accettare come argomento un numero
negativo.
Con un parametro negativo, delle due forme presentate in questo thread
la prima (riportata qui sopra) va in loop, la seconda:
<quote>
int factorial(int n)
{
  // factorial(n) corrisponde a: n*factorial(n-1) dove factorial(0) e'
1;
  int a = 1;
  int j;
  for(j=2;j<=n;++j)
   a *= j;
  return a;
}
</quote>
restituisce come risultato 1, che comunque e' errato, in quanto il
fattoriale di un numero negativo, per definizione, non esiste.
Buon lavoro a tutti.
PS: ho fatto una ricerca su google, e ho trovato molti siti che
riportano, come esempio di funzione ricorsiva, proprio questo calcolo
del fattoriale che inevitabilmente va in loop con argomenti negativi.
Per ovviare a questo inconveniente, ritenete che sia piu' corretto
definire un tipo "naturale" ed usarlo come parametro della funzione
(ottenendo cosi' una segnalazione di errore a compile-time) o testare
la correttezza del parametro a runtime, restituendo "0" o "-1" o NAN o
qualcos'altro e lasciando al programmatore la responsabilita' di
verificare il valore restituito dalla funzione?

 verificare il valore restituito dalla funzione?
A mio avviso testare testare se e' negativo va benissimo! Sappiamo tutti che
i valori vanno da 1 a....... +infinito!!! In pratica se mi esce -6 mi
aspetto che qualche cosa non sia andato bene, magari anche solo un
factorial(20); che sulla mia macchina a 32 bit restituisce un valore
negativo!
Nel primo caso si potrebbe anche testare il valore che si passa, nel secondo
no.
Esistono modi migliori per verificare se il numero ottenuto e' valido oppure
se e' risultato di un overflow! Ad esempio il factorial(30) mi da un
risultato positivo, ma e' per caso attendibile?!? NO!
Un'altra soluzione e' quella di utilizzare una classe per numeri con teorica
possibilita' di arrivare ad un numero infinito di digits:
<CODE>
#include<iostream>
#include"CInfInt.h"
CInfInt factorial(CInfInt n)
{
    CInfInt tmp=n;
    if(!n)n=1;
    while(tmp>1)n*=--tmp;
    return n;
}
int main()
{
    std::cout << factorial(256) << std::endl;
    return 0;
}
</CODE>
<OUTPUT>
+857817775342842654119082271681232625157781520279485619859655650377269452553
1475
8937744029136045140845037588534233658430615719683469369647532228928849742602
5679
6373325633687864426752076267945601879688679715211433077020775266464514647091
8732
6100832876325702818980773671781454170250523018608495319068138257481070252817
5594
5947698703466571273813928620523475680821886070120361108315209350194743710910
1726
9682628616062636624350228409441914084246159360000000000000000000000000000000
0000
0000000000000000000000000000
</CODE>
Purtroppo in questo modo la funzione diventa meno efficace anche se per il
fatt(256) il risultato e' assolutamente immediato!
Incomincio a notare un delay da fattoriale 5000 in poi....
Implementazioni specifiche offrono metodi per controllare l'overflow, ma
queste in molti casi NON sono portabili.
Tommy