ricorsione, s.f.: vedi ricorsione
L’induzione, di cui ho parlato poco tempo fa, è una brutta bestia: non tanto per la complessità del concetto, quanto perché il modo con cui si impiega generalmente l’induzione è piuttosto astratto. Le dimostrazioni per induzione assomigliano spesso a un gioco di prestigio algebrico, con un po’ di operazioni formali. Insomma, qualcosa che funziona sì, ma non ci dà informazioni su cosa sta effettivamente dietro.
La cosa buffa è che però è relativamente semplice trovare spiegazioni sull’induzione, ma almeno per i matematici non ci sono così tante informazioni su un modo in un certo senso simile per risolvere i problemi matematici: la ricorsione. La mia sensazione è che la ricorsione era sempre stata usata dai matematici del passato, ma veniva considerata una tecnica di serie B e quindi snobbata nelle dimostrazioni “ufficiali”. Poi è arrivata l’informatica, dove la ricorsione è parecchio usata; di nuovo però i matematici pensano che una cosa usata dagli informatici non è poi così importante… Ma lasciamo perdere queste disquisizioni, e vediamo come funziona la ricorsione.
Tecnicamente la ricorsione consiste nel risolvere un problema P con dati in ingresso D riconducendosi alla risoluzione del problema P con dati in ingresso D’, dove i dati D’ sono “più semplici” dei dati D. La frasetta magica “ricondursi al caso precedente” ricorre spesso nelle barzellette create dai fisici per prendere in giro i matematici; ma in questo caso la cosa è piuttosto diversa, e molto più seria. Ecco l’esempio canonico di ricorsione, tanto per mettere le cose più in chiaro: il calcolo del fattoriale.
Come probabilmente ricordate, il fattoriale di un numero intero positivo n, indicato con n!, è il prodotto dei numeri da 1 a n. Per convenzione, 0! e 1! sono uguali a 1. Per calcolare n! si può appunto fare il prodotto dei numeri da 1 a n, ma si può anche operare in altro modo. Un informatico per esempio scriverebbe un programma la cui parte principale dice più o meno così: “Per calcolare la funzione “fattoriale di n“, chiamo la funzione “fattoriale di n-1″ e moltiplico il risultato per n.” Chi non è abituato a queste cose fa un balzo sulla sedia: “Ma come fa questo qua a scrivere una cosa del genere? Com’è possibile definire una funzione per mezzo di sé stessa? Non si sovrappongono i pezzi?” Per quanto riguarda la struttura informatica, vi posso assicurare che non ci sono problemi: quello che viene richiamato non è il programma inteso come archetipo ma una sua istanza, insomma un suo clone. Il punto chiave è che dobbiamo essere certi che il procedimento non si espenda all’infinito, oppure che a un certo punto si ritorni al punto di partenza ottenendo così un circolo vizioso. Ma per fortuna questo non è il caso: il numero di cui si deve calcolare il fattoriale continua a ridursi, e prima o poi diventerà 1 (beh, ammesso che l’input sia stato un numero intero positivo. Ma quello del validare i dati in ingresso è un altro tipo di problema: qui si fa matematica, non informatica). Ma noi sappiamo quanto vale il fattoriale di 1! (per la cronaca, quest’ultimo è un punto esclamativo, non il simbolo di fattoriale), cioè 1. In definitiva, basta aggiungere il caso particolare; “Per calcolare la funzione “fattoriale di n“, verifico se n=1; in caso affermativo il risultato è 1, altrimenti, ecc. ecc.”.
Notata la differenza con l’induzione? Lì partivamo da 1 e salivamo fino all’infinito, grazie al quinto postulato di Peano; qui partiamo da un numero qualunque e scendiamo fino a 1. C’è però un altro punto che in genere viene trascurato. L’induzione parte da una formula chiusa, una cioè dove basta infilare il numero e si ottiene il risultato; con la ricorsione non c’è nulla del genere, e anzi trovare una formula chiusa a partire da quella ricorsiva non è sempre così semplice. Tanto per fare un esempio pratico, prendiamo i numeri di Fibonacci. Come ricordate, la loro definizione è ricorsiva: F1 = F2 = 1, e Fn+1 = Fn + Fn-1. È anche possibile avere una formula esplicita per l’n-simo numero di Fibonacci:
dove φ1 è (1+√5)/2 e φ2 è (1-√5)/2. Semplice, no? Vero che ce l’avevate sulla punta della lingua? D’accordo, questo è forse un caso limite: ma in genere ci vuole comunque una certa arte per trovare la formula chiusa corrispondente a una formula ricorsiva.
Nonostante tutto, però, la ricorsione almeno a mio parere è un modo più naturale per trovare la soluzione di tutta una classe di problemi, e quindi dovrebbe essere sempre pronta nella borsa degli attrezzi di un matematico.
Ultimo aggiornamento: 2010-04-01 11:43
Bisognerebbe menzionare che non è sempre possibile trovare la formula chiusa. Dipende dal problema (ad esempio se hai delle divisioni intere con ceil o floor nella formula ricorsiva, la formula chiusa te la scordi).
Ragazzi, vivo in una terra di leghisti e certe cose non le so: mi spiegate che cosa vuol dire avere delle divisioni intere con ceil o floor nella formula ricorsiva?
Grassie.
Pop
@popinga: floor (1,2) = 1; ceil (1,2) = 2. Divisione intera è quella che butta via il resto (alzando il quoziente se si usa ceil() ).
“La ricorsione (…) dovrebbe essere sempre pronta nella borsa degli attrezzi di un matematico”. E infatti c’è.
Il punto è che non si usa nelle dimostrazioni; si usa per dare definizioni. Ad esempio, somma e prodotto sui naturali sono definiti per ricorsione; si dimostra per induzione che sono commutativi e associativi.
Allora si tratta di maniere americane per dire che arrotondo per difetto o per eccesso?
Grazie, .mau.
@popinga: direi più che altro maniere informatiche. Tra l’altro, anche se non c’entra con floor() e ceil(), la ricorsione è tornata in auge appunto con i computer, non foss’altro che perché loro sono bravi a fare tante operazioni semplici :-)
@popinga: neanch’io ho mai sentito dire ceil e floor, e non sono neanche sicura di sapere cosa sono: arrotondamento all’unità superiore e inferiore rispettivamente?
@.mau. “tornata in auge”: sarà la fame, ne riparliamo domani a stomaco pieno.
dopo i fasti di Eulero e dei primi analisti, e il ritorno di fiamma di quelli che volevano trovare bei controesempi (la curva di Peano è definita ricorsivamente), cosa c’è stato?
Ora che ci pensio, io ceil e floor li conosco perché sono comandi TeX, credo di aver sentito chiamare così gli arrotondamenti solo in quel contesto.
Wikipedia è la vostra amica.
La nota 1 dà come riferimento Knuth, in fondo avevo ragione :-)
La cosa che è invece difficilissima da spiegare (agli studenti come agli ingegneri) è che non tutti i problemi/algoritmi che hanno una formulazione/soluzione ricorsiva ne hanno una iterativa.
@.mau.#8: un esempio relativamente recente (1993 circa): la formula di Kontsevich per le curve razionali nel piano è ricorsiva, esattamente come un sacco di roba in geometria enumerativa prima e dopo, negli ultimi due secoli.
Mica è colpa mia se i matematici usano la ricorsione senza venirlo a raccontare a te :-).
In senso più lato, e per parlare di cose che anche tu dovresti aver sentito nominare, i teoremi di punto fisso alla Banach mi sembra abbiano una soluzione ricorsiva.
@marcoxa: iterativo cosa vuol dire? Qui (su xmau.com/notiziole e relativi commenti) se ne impara sempre una.