La Divina Ricorsione (parte 2)


Nel post precedente abbiamo introdotto l’idea alla base della ricorsione ma siamo rimasti in sospeso con la questione non trascurabile di assicurarci l’arresto della procedura ricorsiva.

Per risolvere il problema della ripetizione all’infinito, dobbiamo introdurre un piccolo elemento in più. Calcolando infatti la funzione espressa come la volta scorsa, non abbiamo alcuna condizione di arresto. Abbiamo visto negli algoritmi, che la condizione di arresto è necessaria per ottenere un risultato finale dopo un numero finito di passi di esecuzione.

La definizione corretta è la seguente:

S(N) = N + S(N-1)

S(1) = 1

Che garantisce l’arresto al passo N = 1.  Sono necessarie due espressioni per definire le funzioni ricorsive, la prima che definisce la funzione in termini di sé stessa, e la  seconda che specifica la condizione in cui la funzione restituisce un valore definito. Una funzione espressa in questo modo si legge come segue:

Per N generico, la somma di N è uguale ad N più la somma di N-1; per N = 1 la somma è pari ad 1.

Torniamo allora al caso pratico per N = 3:

S(3) = 3 + S(2) = 3 + 2 + S(1) = 3 + 2 + 1 = 6

Nel caso specifico della somma dei primi numeri naturali, grazie a Gauss, sappiamo che la ricorsione non è necessaria ed è possibile fornire un’espressione matematica non ricorsiva che risolve lo stesso problema:

S(N) = N(N+1)/2

Il punto è che esistono anche espressioni che non sono risolvibili mediante funzioni e che necessitano forzatamente di una espressione ricorsiva, come ad esempio il fattoriale:

F(N) = N F(N-1)
F(0) = 1

e cioè il prodotto dei primi numeri naturali, che in matematica si esprime con un punto esclamativo, N!. E’ un numero che cresce enormemente al crescere di N, ad esempio

10! = 10x9x8x7x6x5x4x3x2x1 = 3.628.800

un numero decisamente grande. Notate la finezza di aver definito lo zero fattoriale uguale ad 1, ci torneremo quando opportuno.

All’aumentare di N il fattoriale cresce vertiginosamente, già 100! è un numero enorme di 157 zeri. Per dare una idea della sua grandezza, la dimensione stimata del’universo osservabile, in metri, è un numero con 26 zeri.

Nel caso del fattoriale, e in moltri altri, non è possibile fornire un’espressione non ricorsiva della stessa formula. Pensate che, per quanto sofisticata sia, ci sono tracce evidenti dell’uso della ricorsione già nel 300 a.C., ad opera dello stesso Euclide. Mettiamo per ora al sicuro questo nuovo potentissimo strumento nella borsa del matematico, lo applicheremo in seguito in un numero considerevole di occasioni, tutte estremamente interessanti.

Annunci
Questa voce è stata pubblicata in Teoria e Pratica e contrassegnata con , , , , , , . Contrassegna il permalink.

7 risposte a La Divina Ricorsione (parte 2)

  1. Andrea ha detto:

    In realtà il fattoriale è rappresentabile per via analitica come funzione non ricorsiva, grazie alla funzione Gamma di Eulero:
    Gamma(N) = (N-1)!
    e quindi come prodotto infinito. Non è però calcolabile con un algoritmo finito che io sappia.

  2. lidimatematici ha detto:

    Vero! Ma per parlare della Gamma di Eulero bisogna prima affrontare i numeri complessi ed il concetto di integrazione, ci arriveremo per gradi …

  3. Pingback: Addizioni e moltiplicazioni … a gogo ! | LidiMatematici

  4. paul spider ha detto:

    c’è un algoritmo di sottrazione? devo controllare i risultati parziali di a – 1 – 2 – 3 -… e fermarmi ad un numero n che sia minore o uguale ad un numero dato m, esiste un sistema più veloce di calcolarlo? grazie 🙂

  5. Pingback: L’eleganza della matematica | LidiMatematici

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...