[Python]Programma Calcolo Fattoriale

[Pacio88]

Sto studiando Python e mi sono imbattuto in questo esercizio.

def Fattoriale(n): 
  if n == 0: 
    return 1 
  else: 
    FattorialeMenoUno = Fattoriale(n-1) 
    Risultato = n * FattorialeMenoUno 
    return Risultato 

Allegato all'esercizio svolto viene mostrato una descrizione del flusso del programma dove n=3:

1.Dato che 3 non è 0, seguiamo il ramo else e calcoliamo il fattoriale di n=3-1=2...
2.Dato che 2 non è 0, seguiamo il ramo else e calcoliamo il fattoriale di n=2-1=1...
3.Dato che 1 non è 0, seguiamo il ramo else e calcoliamo il fattoriale di n=1-1=0...
4.Dato che 0 è 0 ritorniamo 1 senza effettuare ulteriori chiamate ricorsive.
5.Il valore di ritorno (1) è moltiplicato per n (1) e il risultato (1) restituito alla funzione chiamante.
6.Il valore di ritorno (1) è moltiplicato per n (2) e il risultato (2) restituito alla funzione chiamante.
7.Il valore di ritorno (2) è moltiplicato per n (3) e il risultato (6) diventa il valore di ritorno della funzione che ha fatto partire l'intero processo.

Sinceramente questo esercizio che senz'altro sarà banale mi resta difficile capirlo. In particolare non spiego il passaggio dal punto 3 al punto 4 e come poi si svilippi nei passaggi successivi.

C'è qualcuno in grado di essere più chiaro?

P.S. La formula del fattoriale è la seguente n! = n (n-1)!
Esempio: 3! = 3*2*1 = 6 e 5! = 5*4*3*2*1 = 120

Grazie a tutti coloro che mi risponderanno!

[YuYevon]

Pacio88 spiegare come funziona la ricorsione è difficile perché viene sfruttata un'area di memoria, lo stack, gestita dal processore secondo la filosofia LIFO (Last In First Out) il che significa che l'ultimo elemento inserito nello stack (in italiano "pila") è il primo che viene prelevato; è un po' come se avessi una pila di piatti: se ci metti dentro 10 piatti il primo che poi puoi togliere è l'ultimo che hai messo, quello sopra a tutto.

Supponiamo di fare una chiamata tipo fattoriale(5);

viene attivata la funzione fattoriale(5). Poiché 5 non è 0, l'istruzione dell'if (che è il caso base o "banale") non viene eseguita e si passa all'else. L'else che fa? Associa a "fattorialemenouno" il risultato della chiamata alla stessa funzione fattoriale però con l'argomento decrementato di 1, e questa chiamata va nello stack SOPRA quella precedente, quindi nello stack avrai

fattoriale(4)
fattoriale(5)

stessa cosa per fattoriale(4): non essendo 4==0, viene riattivata di nuovo la funzione con 3, quindi abbiamo fattoriale(3)

fattoriale(3)
fattoriale(4)
fattoriale(5)

E così via. Arrivato a 0 (con la chiamata fattoriale(0)) giungiamo al caso base, infatti in quel caso n==0 è vero, quindi non viene attivata un ulteriore function. Nello stack abbiamo quindi, infine:

fattoriale(0)
fattoriale(1)
fattoriale(2)
fattoriale(3)
fattoriale(4)
fattoriale(5)

a questo punto abbiamo detto che fattoriale(0) non attiva ulteriormente la function fattoriale ma restituisce 1 (che è il fattoriale di 0), quindi abbiamo

1
fattoriale(1)
...
fattoriale(5)

a quel punto si riattiva fattoriale(1) che "usa" quello 1 per i suoi calcoli e lo moltiplica per n (che in quella function vale appunto 1) e restituisce n*1, ossia 1, quindi abbiamo

1
1
fattoriale(2)
fattoriale(3)
fattoriale(4)
fattoriale(5)

viene quindi riattivata fattoriale(2) che era stata sospesa e le viene passato il valore restituito da fattoriale(1) (che era 1) e lo moltiplica per n (in questo caso 2) e restituisce 1*n, ossia 2.

1
1
2
fattoriale(3)
fattoriale(4)
fattoriale(5)

fattoriale(3) anche viene riattivata, si prende il 2 della funzione precedente, lo moltiplica per n (3), ottiene 6 e lo restituisce a fattoriale(4), il quale a sua volta prende 6, lo moltiplica per n (4) e restituisce 4*6 (24) a fattoriale di 5

1
1
2
6
24
fattoriale(5)

quindi fattoriale(5), che era la prima funzione attivata con la nostra chiamata, si vede arrivare 24, lo prende e lo moltiplica per 5, ottenendo 120 che è esattamente 5!.

[Pacio88]

Grazie!!Adesso finalmente sono riuscito a capire. Ma l'utilizzo di funzioni ricorsive è frequente nella programmazione?

[robyonrails]

In generale come puoi dire se un approccio è frequente? E' chiaro che ci sono diversi (e.g.: visualizzazione dell'albero delle directory) problemi che con la ricorsione si possono rappresentare in modo elegante ed immediato.

Sicuramente l'utilizzo non è frequentissimo se utilizzi linguaggi imperativi, ma il discorso cambia quando entri nel mondo del paradigma funzionale.

[YuYevon]

E comunque in ogni caso è un argomento che devi assolutamente assimilare per bene.

[billiejoex]

Grazie!!Adesso finalmente sono riuscito a capire. Ma l'utilizzo di funzioni ricorsive è frequente nella programmazione?

Nei linguaggi funzionali in genere si ma in Python no.
In Python la ricorsione è lenta ed in genere evitata come la peste preferendo l'iterazione al suo posto.

Personalmente, sebbene sappia la teoria che sta alla base, ogni volta che vedo una funzione ricorsiva ci devo spendere un po' di tempo per comprenderla.
Anche se questo può sembrare più ordinato e leggibile:

def fattoriale(n):
    if n == 0:
        return 1
    return n * fattoriale(n - 1)

...preferisco di gran lunga questo:

def fattoriale(n):
    result = 1
    factor = 2
    while factor <= n:
        result *= factor
        factor += 1
    return result

...del resto "explicit is better than implicit" (cit. dallo Zen di Python), e per come la vedo io tra le due funzioni la prima non è esplicita quanto la seconda.

[robyonrails]

MMmh io personalmente trovo strana questa tua difficoltà: il caso base si individua subito e il passo induttivo altrettanto.

E' vero che in Erlang forse si vede un po' meglio

fac(0)- > 1;
fac(X) -> X * fac(X-1).

ma considerando che in Common Lisp ottieni

(defun fac(x)
           (if (= x 0)
               1
               (* x (fac (- x 1)))

(anche se devo ammettere che si vede bene anche qui, questione di parentesi)

vedrai che in Python non è poi così male

def fattoriale(n):
    if n == 0:                                    # caso base
        return 1
    return n * fattoriale(n - 1)             # passo induttivo

[Pacio88]

Perdonatemi l'ignoranza, ma che cosa sono Erlang e Common Lisp?

[pallinopinco]

Sono due linguaggi di programmazione.

In Haskell:

fac n = if n > 0 then n * fac (n-1) else 1

[Pacio88]

Perdonatemi ancora l'ignoranza
Ma questi linguaggi sono molto diffusi?E per quale sviluppo di software vengono utilizzati?