Un noto tipo di approccio alla risoluzione dei problemi consiste in una analisi che conduce alla scomposizione del problema in sottoproblemi più semplici. Può essere descritto nel modo seguente
Risolvere il problema P:
se è nota una risoluzione di P
allora
applicarla
altrimenti
scomporre P in sottoproblemi P(1), P(2),...,P(n)
risolvere il problema P(1)
......
risolvere il problema P(n)
Può accadere che almeno uno dei sottoproblemi sia lo stesso problema in esame. Si ha allora a che fare con una analisi detta "ricorsiva" che, quando è corretta, può essere estremamente proficua. Un esempio interessante di applicazione "ricorsiva" del metodo descritto si ha nel famoso Paradosso di Zenone dell'impossibilità del movimento. In sintesi lo si può formulare nel modo seguente:
Andare da A fino a B: andare da A fino al punto medio tra A e B andare dal punto medio tra A e B fino a B.Il problema 'andare da ... a ...' è sia il problema da risolvere sia ciascuno dei due sottoproblemi in cui esso viene scomposto. Tuttavia ad una tale descrizione, che sembra mostrare un procedimento risolutivo, non corrisponde in realta` alcun procedimento effettuabile. In particolare non vi è descritta alcuna prima azione. Questo primo esempio evidenzia un modo inefficace di applicare la ricorsività come tecnica per descrivere procedimenti, anche se permette di mettere in rilievo alcuni aspetti problematici della situazione. Lo stesso metodo di scomposizione in sottoproblemi ha un aspetto ricorsivo. Infatti è applicato anche per risolvere ciascun sottoproblema. L'espressione 'risolvere il problema ... ' compare sia a titolo della descrizione sia al suo interno, là dove il testo "richiama" se stesso.
Si possono portare esempi di altre situazioni in cui è evidente la struttura ricorsiva: la ripresa televisiva di un televisore che trasmetta quella stessa ripresa, l'amplificazione di un suono registrato dall'altoparlante all'uscita dello stesso amplificatore, una cattiva definizione come "Si dice moltitudine una pluralità tale che, tolto un elemento, si ha ancora una moltitudine", la favola "C'era una volta uno scrittore che stava scrivendo una favola. Iniziava così : << C'era una volta uno scrittore che stava scrivendo una favola. Iniziava così : << C'.....".
La ricorsività è utilizzata in filosofia anche con effetti meno eclatanti di quelli ottenuti da Zenone con i suoi paradossi. Alessandro di Afrodisia attribuisce ad Aristotele il cosiddetto argomento del "terzo uomo" con cui si vuole criticare l'idealismo platonico. In sintesi, se fosse vero che per comprendere il concetto di uomo è necessario possedere l'idea di uomo, allora ci vorrebbe anche un'idea di somiglianza tra l'uomo e l'idea-di-uomo; ma allora occorrerebbe anche un'idea di somiglianza tra l'idea-di- somiglianza-tra-l'uomo-e-l'idea-di-uomo e l'uomo-e-l'idea- di-uomo; e così via. A. Dumas figlio affermava, ricorsivamente, che:
tutte le generalizzazione sono pericolose, compreso questa.Dai diversi esempi proposti si comprende come questo stile espressivo e di pensiero debba essere in qualche modo regolato perché possa essere usato efficacemente, per risolvere problemi, come avviene in matematica, e non solo per evidenziare la problematicità di certe situazioni.
E` bene, a questo punto, distinguere chiaramente tra ricorsività e ripetitizione. Il testo
dì 'ripeti', dì 'ripeti', ..........., dì 'ripeti'che si può sintetizzare ad esempio con
finché non sei stanco di parlare
dì 'ripeti'
si basa su una struttura linguistica ripetitiva del tipo
'.....'oppure
'finché ......
..........'.
Diversamente
Dì la parola:
se non sei stanco di parlare
allora
dì la parola
dì 'ripeti'
è una descrizione ricorsiva.
Il primo testo ha una struttura linguistica, lo si legge senza uscirne. Il secondo
ha una struttura meta-linguistica, per essere seguito richiede la capacità di
uscirne. Entrambi descrivono lo stesso procedimento. In quest'altro caso Dì
la parola: se non sei stanco di parlare allora dì la parola dì 'ripeti' seguendo
alla lettera il testo, non si riesce invece a pronunciare alcunché pur restando
impegnati nella lettura stessa, iniziando ad iniziare finché non ci si è stancati.
Il linguaggio formale dei numeri naturali può essere descritto in modo ricorsivo. Un numero naturale è: una cifra oppure una cifra seguita da un numero naturale. In generale un linguaggio formale consiste di tutte quelle espressioni che, composte con i simboli di un "alfabeto", o si trovano in un "dizionario" o si possono ottenere da un'espressione dello stesso linguaggio mediante trasformazioni soggette a delle regole "grammaticali" esplicitate. Nel caso dei numeri naturali le cifre costituiscono sia l'alfabeto sia il dizionario delle espressioni di base e c'è una sola regola grammaticale: mettere una cifra davanti a un numero. Ad una tale descrizione dei numeri naturali sfugge naturalmente l'aspetto semantico, cioè come tali espressioni si applichino alla realtà o ad altri sistemi di segni; allo stesso modo la logica di cui ci si serve in matematica è un linguaggio formale, un modello del nostro ragionamento, e quindi una sua semplificazione, in cui predomina totalmente l'aspetto sintattico. Uno schema di ragionamento logico è una espressione che o appartiene ad uno dei possibili sistemi di assiomi della logica, come potrebbe essere il principio del terzo escluso 'p o non p', o si può ricavare da schemi di ragionamento logico, applicando cioè regole, come ad esempio quella del modus ponens, esplicitate in uno dei possibili sistemi di regole di inferenza deduttiva. Ogni linguaggio formale, ovvero ogni sistema formale o sistema assiomatico-deduttivo, è dunque descrivibile con metodo ricorsivo:
Trovare se l'espressione x appartiene al linguaggio L:
se x non sta nel "dizionario" di L
allora
trovare y(1),...,y(n) in modo che x si ottenga da quelli mediante l'applicazione delle regole "grammaticali" di L
trovare se l'espressione y(1) appartiene a L
.....
trovare se l'espressione y(n) appartiene a L.
In questa descrizione si può intravedere anche il concetto
di dimostrazione. Aristotele ancor prima di Euclide si era reso conto che esso
andava approfondito e il processo di dimostrare sottoposto a regole. Infatti
lo schema
dimostrare l'affermazione A: trovare delle affermazioni B(1), B(2), ..., B(n) tali che A sia logicamente deducibile da quelle dimostrare l'affermazione B(1) ..... dimostrare l'affermazione B(n)rappresenta procedimenti che certamente non terminano. Occorre dunque stabilire dei principi primi, degli assiomi, che diano termine alla catena dei passi che costituiscono la dimostrazione
dimostrare l'affermazione A:
se A non è un un assioma
allora
trovare delle affermazioni B(1), B(2), ..., B(n) tali che A sia deducibile logicamente da quelle
dimostrare l'affermazione B(1)
......
dimostrare l'affermazione B(n).
Lo stile ricorsivo
del processo dimostrativo subisce dunque una prima regolazione. Lo schema di
induzione matematica, un pilastro nel pensiero matematico, è molto in odore
di ricorsività. Dimostrare per induzione matematica significa seguire lo schema
dimostrare l'affermazione aff(n) dipendente da un parametro n, naturale: dimostrare l'affermazione aff(1) dimostrare l' affermazione aff(n-1) ===> aff(n)Evidentemente non si tratta di uno schema ricorsivo se non in quanto dimostrazione. E` piuttosto il criterio di "verifica" che utilizziamo per rinforzare la nostra credenza in questo tipo di schema dimostrativo che ha un aspetto ricorsivo
aff(n) è vera perché:
se n = 1 allora il caso è stato dimostrato in particolare
altrimenti
aff(n-1) è vera perché ... da (aff(n-1)===>aff(n)) e aff(n-1) si deduce aff(n)
Un altro metodo molto utilizzato in matematica può essere descritto ricorsivamente,
quello delle approssimazioni successive.
Cercare una soluzione di un problema P sapendo che è compresa tra a e b:
se |a-b| è minore di un prefissato ε 'piccolo a piacere'
allora
una soluzione di P, approssimata, è a
altrimenti
se (a+b)/2 è troppo grande per risolvere P
allora
cercare soluzione di P sapendo che è compresa tra a e (a+b)/2
altrimenti
cercare soluzione di P sapendo che è compresa tra (a+b)/2 e a
Tale metodo può essere confrontato con il paradasso di Zenone
sull'impossibilità del movimento.
Si propongono nel seguito alcuni elementi di riflessione intorno ad argomenti che solitamente si affrontano nei corsi di matematica. Per calcolare la somma di più numeri, ad esempio, si suggerisce generalmente di applicare il procedimento seguente: sommare il secondo numero al primo finché ci sono altri numeri aggiungere alla somma già calcolata il numero successivo. Tale descrizione è basata sulla struttura linguistica della ripetizione. Una versione ricorsiva è la seguente:
sommare n numeri:
se n = 2
allora
aggiungere al primo numero il secondo
altrimenti
sommare i primi n-1 numeri aggiungere alla somma ottenuta l'ultimo numero.
Analogamente la potenza intera di un numero può essere definita in modo iterativo:
an = a*a*a*....*a (n volte)oppure in modo ricorsivo:
1 se n=0 e a<>0
an =
an-1 * a se n > 0
Può essere interessante rivedere in modo ricorsivo come scomporre n, numero
naturale, in fattori primi:
cercare n1 ed n2, diversi da 1 e da n, tali che n1*n2=n:
se sono stati trovati
allora
scomporre n1 in fattori primi
scomporre n2 in fattori primi
altrimenti
se n<>1
allora
n è un fattore primo
Applicando il procedimento appena descritto a 12 si possono registrare i passi
seguenti:
scomporre 12: 2*6=12
scomporre 2: 2 è un fattore primo
scomporre 6: 2*3=6
scomporre 2: 2 è un fattore primo
scomporre 3: 3 è un fattore primo
Qui l'indentazione,
cioè lo stile di spostare il margine sinistro, serve per indicare l'inizio di
una interruzione momentanea del lavoro iniziato allo scopo di intraprendere
una ulteriore applicazione del procedimento. Sempre più proposto nell'insegnamento
è il classico algoritmo di Euclide per calcolare il M.C.D. tra due numeri naturali
che, in forma ricorsiva, può essere scritto nel modo seguente:
Calcolare il M.C.D. tra a e b:
se a=b
allora
il M.C.D. è a
altrimenti
se a>b
allora
il M.C.D. è il M.C.D. tra a-b e b
altrimenti il M.C.D. è il M.C.D. tra a e b-a
E` ciò
che si potrebbe anche scrivere
a se a=b
M.C.D.(a,b)= M.C.D.(a-b,b) se a>b
M.C.D.(a,b-a) altrimenti
con formalismo matematico compatto ed elegante. Possiamo anche in
questo caso provare a descrivere i passi per
calcolare il M.C.D. tra 12 e 16:
calcolare il M.C.D. tra 12 e 4:
calcolare il M.C.D. tra 8 e 4:
calcolare il M.C.D. tra 4 e 4:
il M.C.D. è 4
Anche i sistemi di numerazione in base diversa
da dieci sono sempre più spesso presenti tra gli argomenti proposti nell'insegnamento.
Vediamo come si possa spiegare in modo ricorsivo come
trasformare, da base dieci ad altra base, un numero:
se numero <> 0
allora
trasformare il quoziente tra numero e base nell'altra base
registrare il resto tra numero e base tradotto nelle cifre dell'altra base
Applichiamo il procedimento ad esempio per
trasformare 9 in base due:
trasformare 4 in base due:
trasformare 2 in base due:
trasformare 1 in base due:
trasformare 0 in base due:
registrare 1
registrare 0
registrare 0
registrare 1.
La combinatoria è per sua natura un dominio del pensiero ricorsivo.
Infatti per
permutare una lista di n oggetti:
se ci sono oggetti
allora
estrarre un oggetto e porlo in testa
permutare il resto e porlo in coda
altrimenti
la permutazione è una lista vuota.
oppure
per disporre n oggetti k alla volta:
se ci sono oggetti e k > 0
allora
estrarre un oggetto
disporre gli n-1 oggetti restanti k-1 alla volta
altrimenti
la disposizione è una lista vuota.
Il numero
delle disposizioni di n oggetti presi k alla volta saranno dunque
1 se k=0
Dn,k =
n * Dn-1,k-1 se k <= n
Invece per
combinare n oggetti k per volta:
se n = k oppure k = 0
allora
la combinazione è la lista costituita dagli stessi oggetti oppure è vuota
altrimenti
combinare gli oggetti, tolto il primo, k-1 per volta
inserire il primo oggetto in testa alle combinazioni ottenute
combinare gli oggetti, tolto il primo, k per volta
Ad esempio si vogliano combinare abcd 2 alla volta. Otterremo:
ab, ac, ad, bc, bd, cd.Il numero delle combinazioni di n oggetti presi k alla volta, come i numeri del triangolo di Pascal-Tartaglia, ovvero i coefficienti binomiali, saranno dunque definiti ricorsivamente da:
1 se k=0 oppure n=k
Cn,k=
Cn-1,k-1 + Cn-1,k se k < n
La successione di Fibonacci,
definita sinteticamente come
1 se i = 1 , 2
f(i) =
f(i-2) + f(i-1) se i > 2
è storicamente associata ad un problema, quello della crescita di una famiglia
di conigli che si riproducono secondo certe regole, che si risolve facilmente
proprio con stile ricorsivo.
In generale i modelli matematici per rappresentare la crescita di popolazioni si costruiscono molto più facilmente ricorrendo ad uno schema ricorsivo, come nel caso più semplice in cui, detto n il numero di individui in funzione del tempo:
n0 se t=t0
n(t + dt) =
n(t) + a*n(t) se t>t0
essendo a la differenza tra tasso di natalità e tasso di mortalità. Per concludere
si può vedere come lo schema di linguaggio- pensiero ricorsivo sia di utilità
per risolvere semplicemente un problema complesso come il seguente:
Calcolare
la probabilità che tra n persone non ci siano nati nello stesso giorno dell'anno.
Detta p(n) la soluzione, evidentemente p(2)=1-1/365. La probabilità che Tizio non sia nato lo stesso giorno degli altri, supposto che tra questi non ci siano nati lo stesso n-1 giorno, vale (1- 1/365) e quindi
p(n) = p(n-1) * (1 - 1/365)n-1