La ricorsività in matematica
La ricorsività permette di definire una successione numerica in funzione del termine che lo precede. Questa forma è detta ricorsiva.
La forma ricorsiva è detta anche induttiva, perché la ricorsività è strettamente legata al principio di induzione matematica.
La successione definita ricorsivamente
Una successione è definita ricorsivamente ( induttivamente ) se
- Si definiscono i primi k valori iniziali della successione ( passo base )
- Si definisce una regola che determina tutti i valori della successione a partire dai k valori iniziali ( passo induttivo )
Ovviamente, il valore iniziale k è un numero intero e deve essere almeno uno o più di uno.
$$ k \ge 1 $$
Se fosse k fosse zero non avrei alcun valore iniziale e la formula sarebbe inutile.
Un esempio pratico
Ho una successione numerica con le somme dei numeri naturali da 1 a 100.
$$ {a_n} = \sum_{i=1}^{100} =(1)+(1+2)+(1+2+3)+(1+2+3+4)+... $$
$$ {a_n} = \sum_{i=1}^{100} = 1+3+6+10+... $$
Per calcolare il valore del 100-esimo termine della successione a100 devo calcolare tutti i 99 termini precedenti.
E' un bel calcolo da fare mano...
Per ogni termine dovrei sommare tutti i termini precedenti:
$$ a_1=1 \\ a_2=1+2=3 \\ a_3=1+2+3=6 \\ a_4=1+2+3+4=10 \\ \vdots $$
Fortunatamente, grazie alla ricorsione posso evitare di sommare gli stessi numeri più volte.
Definisco una formula che un numero naturale n con l'elemento precedente della successione an-1
$$ a_n = a_{n-1}+n $$
Nei primi quattro numeri k=4 sembra funzionare
$$ a_1=a_0+1=0+1=1 \\ a_2=a_1+2=1+2=3 \\ a_3=a_2+3=3+3=6 \\ a_4=a_3+4=6+4=10 \\ \vdots $$
In questo modo non è necessario sommare gli 1+...n-1 numeri precedenti ogni volta.
Basta sommare l'ultimo numero n con la somma del termine an-1 precedente.
Come funziona la ricorsione
Una funzione ricorsiva richiama se stessa più volte.
Si tratta di una tecnica molto usata nella programmazione informatica perché riduce la quantità di codice per effettuare i calcoli.
Nella ricorsione il problema originario viene suddiviso in sottoproblemi.
Perché? I sottoproblemi sono più semplici da risolvere. Hanno minori dati in input da elaborare.
E' però necessario che i sottoproblemi abbiano la stessa struttura del problema originario.
Esempio. La somma da 1 a 5 e la somma da 1 a 8 hanno la stessa struttura. Lo stesso qualsiasi altra somma da 1 a 99, da 1 a 1000, ecc.
Un algoritmo esegue la funzione ricorsiva con istanze (dati) differenti per risolvere i singoli sottoproblemi.
Poi, mette insieme i risultati dei sottoproblemi per ottenere la soluzione al problema di origine.
Un algoritmo di questo tipo è detto algoritmo ricorsivo.
Nota. La ricorsione riduce molti calcoli ripetitivi. Tuttavia, non è sempre la soluzione migliore. E' comunque preferibile trovare una formula chiusa che calcoli il risultato finale in una sola operazione. Non è sempre possibile... ma vale la pena provarci.
La formula chiusa
Cos'è una formula chiusa
Una formula chiusa definisce una successione senza usare i termini precedenti della successione.
Non è sempre possibile trovarla... ma se si trova il vantaggio è notevole.
Esempio
Questa è una successione ricorsiva
$$ a_n = a_{n-1}+n $$
La formula chiusa della successione ricorsiva è la seguente:
$$ a_n = \frac{n(n+1)}{2} $$
Come trovare una formula chiusa
Seguendo il metodo sperimentale della scienza posso:
- Osservare i primi k termini della successione numerica
- Trovare una formula matematica in grado di ripetere la successione dei k-termini tale e quale.
- Confermare la formula tramite il principio di induzione matematico dei numeri naturali.
Se la formula è confermata con il principio di induzione allora è valida per tutti i numeri. Non solo per i primi k termini.
Nota. Spesso non è facile trovare la soluzione osservando i primi k termini di una successione. In questi casi, posso cercare la formula chiusa della successione ricorsiva anche tramite il metodo dell'equazione caratteristica della relazione ricorsiva. Se esiste una soluzione del tipo rn, questo algoritmo permette di trovarla.
Un esempio pratico
Riprendo la successione della somma dei numeri naturali da 1 a 100.
Eccola definita in forma ricorsiva
$$ a_n = a_{n-1}+n $$
Osservo i primi k=5 numeri della successione
$$ a_1=1 \\ a_2=3 \\ a_3=6 \\ a_4=10 \\ a_5=15 \\ \vdots $$
Poi cerco una formula per ottenere gli stessi risultati.
Ad esempio, l'espressione matematica n(n-1)/2
$$ a_n = \frac{n(n+1)}{2} $$
La formula sembra funzionare correttamente sui primi k=5 termini della serie.
$$ a_1 = \frac{1(1+1)}{2} = 1 \\ a_2 = \frac{2(2+1)}{2} = 3 \\ a_3 = \frac{3(3+1)}{2} = 6 \\ a_4 = \frac{4(4+1)}{2} = 10 \\ a_1 = \frac{5(5+1)}{2} = 15 $$
Tuttavia, non è detto che funzioni per tutti i numeri naturali fino a 100.
Come posso fare per saperlo?
Potrei ripetere l'esperimento fino a k=100 ma sarebbe troppo dispendioso.
Nota. Inoltre, se dovessi dimostrare la formula su infiniti elementi non potrei comunque farlo. Sarebbe impossibile.
Fortunatamente, posso ottenere lo stesso risultato dimostrando la formula con il principio di induzione matematica dei numeri naturali.
Verifico la base induttiva della formula per k=1.
$$ a_n = \frac{n(n+1)}{2} $$
$$ a_1 = \frac{1(1+1)}{2} = 1 $$
E' lo stesso risultato che otterrei con la sommatoria tradizionale
$$ {a_1} = \sum_{i=1}^{1} a_i = 1 $$
Quindi, la base induttiva della formula è vera.
Ora devo verificare se anche il passo induttivo è vero.
Ipotizzo che la formula sia vera per i primi k elementi ( ipotesi ).
$$ P(k) = \frac{k(k+1)}{2} $$
Devo dimostrare che sia vera anche per il k+1 elemento successivo ( tesi ).
$$ P(k+1) = \frac{(k+1)((k+1)+1)}{2} = \frac{(k+1) \cdot (k+2) }{2} $$
Dove k è un numero intero qualsiasi minore di n=100.
$$ 1+2+3+...+k = \frac{k(k+1)}{2} $$
Aggiungo (k+1) a entrambi i membri dell'equazione
$$ 1+2+3+...+k+(k+1) = \frac{k(k+1)}{2} +(k+1) $$
$$ 1+2+3+...+k+(k+1) = \frac{k(k+1)+2(k+1)}{2} $$
Al secondo membro entrambi i termini al denominatore sono moltiplicati per (k+1).
Quindi, posso riscrivere il denominatore in questa forma equivalente
$$ 1+2+3+...+k+(k+1) = \frac{(k+1) \cdot (k+2)}{2} $$
E' esattamente la formula P(k+1) che dovevo dimostrare.
$$ 1+2+3+...+k+(k+1) = P(k+1) $$
Nota. La formula P(n) è $$ a_n = \frac{n(n+1)}{2} $$ Quindi, per l'elemento successivo P(n+1) diventa $$ a_{n+1} = \frac{(n+1)((n+1)+1)}{2} = \frac{(n+1)(n+2)}{2} $$ E' lo stesso risultato dimostrato per induzione. Se vale per l'elemento k+1 vale per qualsiasi altro elemento successivo.
La formula rispetta il principio di induzione.
Quindi, posso usare la formula P(k) per calcolare la somma dei primi 100 numeri naturali con k=100.
$$ P(100) = \frac{100(100+1)}{2} = \frac{100(101)}{2} = \frac{10100}{2} = 5050 $$
La somma dei numeri naturali da 1 a 100 è 5050.
Nota. Ovviamente posso usare la formula chiusa per qualsiasi altro numero naturale. Non solo per k=100. Ad esempio, k=1000, k=915, ecc. La formula chiusa è stata confermata dal principio di induzione. E' quindi utilizzabile per qualsiasi numero naturale.
E così via.
