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.