La Divina Ricorsione (parte 1)

In un post precedente, abbiamo messo al sicuro nella nostra borsa degli attrezzi del matematico uno strumento prezioso, l’algoritmo. Abbiamo detto che gli algoritmi sono strumenti potenti per effettuare calcoli che non possono essere risolti mediante una semplice funzione matematica, ma che necessitano di essere svolti in una serie di passi successivi.

La sequenza di questi passi è detta iterazione ed ogni algoritmo necessita di una condizione specifica che ne assicuri la terminazione. Nell’esempio della volta scorsa, questa condizione è l’uguaglianza del numero calcolato con quello pensato dal nostro amico.

Le funzioni, lo ricordiamo, sono espressioni che, a partire da un certo numero di variabili, restituiscono uno o più risultati. Un esempio è la funzione:

f(x) = 2x

che prende in ingresso la variabile x e ne restituisce il doppio, ad esempio f(5) = 10. Abbiamo visto che questa funzione, se applicata ai numeri naturali pari, è la biiezione che consente di collegare ogni numero naturale dispari al corrispondente pari.

In particolari condizioni è possibile esprimere mediante una funzione calcoli che richiedono una sequenza di iterazioni. Facciamo un caso pratico, riprendendo il calcolo della somma dei primi N numeri naturali. Supponiamo di non conoscere la formula di Gauss, e di partire da un altro punto di vista: diciamo che la funzione che stiamo cercando sia uguale ad una funzione generica S(N). Ora, se la somma dei primi N numeri naturali è S(N), la somma dei primi N+1 numeri è S(N+1). Ma sappiamo che la somma dei primi N+1 si ottiene aggiungendo N+1 alla somma dei primi N numeri, e cioé:

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

Vedete la finezza ? Stiamo esprimendo una funzione  in termini di sé stessa. Funzioni di questo tipo si dicono ricorsive, ed occupano un posto fondamentale nella matematica, per potenza espressiva ed eleganza. Quando esprimimamo una funzione in modo ricorsivo usiamo una notazione estremamente sintetica per un oggetto molto complesso.

Riscriviamo l’espressione ricorsiva in modo più compatto

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

e applichiamola al caso S(3):

S(3) = 3 + S(2) = 3 + 2 + S(1) = 3 + 2 + 1 + S(0) = 3 + 2 + 1 + 0 + S(-1) = …..

e così via all’infinito. Senza una condizione di terminazione, non solo la funzione ricorsiva non è corretta, ma se la eseguissimo al calcolatore, questo non si arresterebbe mai, andando avanti all’infinito.

Volete un esempio visivo di ricorsione ? Mettetevi in mezzo a due specchi o inquadrate la tv con la telecamera attaccata alla tv stessa e godetevi lo spettacolo della vostra immagine riflessa nella vostra immagine riflessa nella vostra immagine e così via fino all’infinito.

Ma se l’effetto ricorsione all’infinito è visivamente interessante ed affascinante, in matematica è decisamente meno desiderabile. Come ne usciamo, dite ? Lo vediamo la prossima volta …

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

8 risposte a La Divina Ricorsione (parte 1)

  1. Pingback: La Divina Ricorsione (parte 2) | LidiMatematici

  2. Pingback: Le Torri di Hanoi (parte 1) | LidiMatematici

  3. Pingback: Le Torri di Hanoi (parte 2) | LidiMatematici

  4. Pingback: Numeri primi e Massimo Comun Divisore | LidiMatematici

  5. Pingback: MCD e Ricorsione | LidiMatematici

  6. Pingback: Fibonacci e Ricorsione | LidiMatematici

  7. Pingback: Benoit Mandelbrot e la geometria frattale | LidiMatematici

  8. Pingback: Le espressioni regolari | LidiMatematici

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *