Strutture ricorsive e autoreferenziali

Durante una giornata ci si trova spesso di fronte a problemi logici da risolvere

o fenomeni da analizzare con attenzione e quello che si tende il più delle volte a fare

è di costruire un procedimento lineare da seguire che, come una retta, partendo da

un punto iniziale giunga ad una conclusione o ad un risultato finale.

Esistono però dei casi particolari in cui questo percorso lineare non può

sussistere ma deve forzatamente deviare piegandosi o ramificarsi in

sottoprocedure. Per quanto riguarda il primo caso può accadere che, deviando, un

procedimento si ripieghi su se stesso portando inizio e fine a coincidere in uno

stesso punto. Cercando così di utilizzare tale procedura nella risoluzione di un

problema ci si troverebbe in un dato istante del tutto inaspettatamente di fronte

al problema di partenza rendendo evidente il fatto che la procedura o il problema

stesso contengano un richiamo più o meno esplicito verso il proprio inizio,

essendo dunque autoreferenziali.

Anche se ci si trovasse di fronte ad un procedimento ramificato ,che si

suddivide cioè in sottoprocedure di ordini gerarchici via via inferiori, potrebbe

verificarsi un altro fenomeno altrettanto particolare. Potrebbe infatti accadere

che le sottoprocedure siano esatte copie della procedura di partenza dalla quale si

ramificano generando così quel fenomeno definito come ricorsività. Utilizzando

tale procedura ricorsiva nella risoluzione di un problema ci si ritrova più volte di

fronte a sottoproblemi del tutto identici al problema di partenza ma in esso

contenuti.

I due fenomeni appena presentati risultano a mio parere strettamente legati da una

caratteristica comune: sia un procedimento autoreferenziale che uno ricorsivo presentano infatti

un richiamo verso se stessi. Attraverso l’autoreferenza il richiamo si genera su uno stesso livello

gerarchico mentre con la ricorsività il richiamo è effettuato su più livelli gerarchici.

Ho deciso di caratterizzare ciascuna parte con una figura che ne evidenziasse l’essenza: il

nastro di Möbius per l’autoreferenza e il triangolo di Sierpinski per la ricorsività.

Processi chimico – biologici

autoreferenziali Processi e algoritmi

ricorsivi

Figure e strutture

autoreferenziali

Autoreferenza Ricorsività Frattali

Autoreferenza

nel pensiero

Procedure

autoreferenziali Figure e strutture

ricorsive 4

Calcolo fattoriale (Programma Java)

Calcolo matriciale (Programma VB)

Processi e algoritmi ricorsivi Programmazione ricorsiva Frattale di Mandelbrot (Programma VB)

Triangolo di Sierpinski

Frattali non biomorfi

Sei personaggi in cerca d’autore

Il fu Mattia Pascal

Pirandello Ricorsività Frattali

Shakespeare - Hamlet

Beckett - Waiting for Godot

Strutture ricorsive in letteratura Frattali biomorfi

Strutture ricorsive presenti in natura

Figure e strutture ricorsive Ricorsione nell’arte Alberi

Montagne

Effetto Droste Nuvole

M.C. Escher

Metabolismo DNA - proteine

Meccanismi di autoregolazione

Metabolismi cellulari Autoreferenza nell’arte

Figure e strutture

Processi chimico – biologici autoreferenziali

autoreferenziali Strutture autoreferenziali in letteratura

Pavese - Feria d’agosto

Beckett - Waiting for Godot

Autoreferenza

Nietzsche - Filosofia dell’eterno ritorno x

Schopenhauer - Autoreferenza della volontà Derivazione e

Procedure matematiche

Pensiero filosofico Procedure autoreferenziali

Autoreferenza nel pensiero Procedure logiche

Paradosso di Epimenide 5

Magritte - L’uso della parola I

Wittgenstein Processi e algoritmi

Automatizzazione procedure di calcolo ricorsivi

matematiche con funzioni ricorsive Programmazione ricorsiva

Calcolo del determinante di una matrice quadrata Richiamo ricorsivo alla funzione per il

calcolo del determinante

Inizio

F V

Calcolo determinante della matrice Calcolo dei complementi algebrici di

Dimensione

di 2° ordine una riga della matrice

matrice > 2 Scomposizione in matrici di 1

ordine inferiore

Calcolo determinante delle

matrici di ordine inferiore

Somma dei prodotti degli elementi

della riga scelta per i rispettivi

complementi algebrici

Calcolo del fattoriale di un numero n Richiamo ricorsivo alla funzione per il

calcolo del fattoriale

Inizio

F V Il Fattoriale di N è uguale a N per il

Il Fattoriale di 0 è uguale a 1 N <> 0 fattoriale di N-1

Disegno del frattale di Mandelbrot Inizio

Selezione di un punto P del piano

0

Traslazione del punto P in Z

0 Richiamo ricorsivo alla funzione per la

traslazione del punto (Z viene passato

N = N+ 1 alla funzione come P )

|OP | > 2 0

0

OR

N > 100

Selezione del colore di P in base a N 6

0 Processi e algoritmi

Automatizzazione di procedure matematiche ricorsivi

tramite funzioni ricorsive

Avendo definito brevemente nell’introduzione il concetto di Programmazione ricorsiva

ricorsività vediamo ora come esso possa essere applicato efficacemente

nell’automatizzazione di procedure di calcolo nell’ambito della

programmazione.

Dato un problema risulta essere abbastanza naturale cercarne

una rappresentazione astratta, cioè cercare di assimilare il problema

specifico ad una categoria più generale di problemi che, una volta

individuata una procedura di risoluzione adeguata e funzionale, possano

portare alla risoluzione, per analogia, di tutti i casi specifici. In secondo

luogo nel creare un algoritmo risolutivo si tenderà il più delle volte a

modularizzare il problema di partenza, si cercherà cioè di suddividere il

problema in sottoproblemi via via più semplici per i quali si possono

individuare o già si conoscono delle soluzioni facilmente calcolabili.

Scomponendo il problema può capitare in taluni casi che i

sottoproblemi siano esatte copie del problema di partenza (come è stato

spiegato nell’introduzione), ciò permette di esprimere un dato problema

in funzione di se stesso rendendo possibile lo sviluppo di un algoritmo

ricorsivo per la sua risoluzione.

Un esempio di un problema che può essere chiaramente

espresso in funzione di se stesso è quello della valutazione della mossa

migliore nel gioco degli scacchi, infatti la mossa migliore per un giocatore

è quella che lascia l’avversario nella situazione più difficile. Per valutare la

bontà di una mossa allora si può pensare di eseguire la mossa e poi di

valutare la situazione dal punto di vista dell’avversario che cercherà di

capire quale è la sua mossa migliore generando un richiamo ricorsivo alla

procedura.

In matematica sono molti i problemi e le procedure che possono

essere espressi in maniera ricorsiva e quelli da me presi in esame in

questo percorso sono solo alcuni esempi che mi sono divertito a realizzare

nel corso di questi ultimi due anni di liceo. La prima volta che mi sono

imbattuto in una procedura matematica ricorsiva stavo realizzando un

programma in VisualBasic che fosse in grado di calcolare il determinante di

una qualsiasi matrice quadrata.

Analizziamo ora brevemente il problema:

 

a a

•  

 1

,

1 1

, 2

data una matrice di 2° ordine: A  

a a

 

2 ,

1 2 , 2 a a

    

1

,

1 1

, 2

il suo determinante si calcola: det A a a a a

1

,

1 2 , 2 1

, 2 2 ,

1

a a

2 ,

1 2 , 2  

a a a

 

1

,

1 1

, 2 1

, 3



•  

data una matrice di ordine superiore (es. 3° ordine): A a a a

2 ,

1 2 , 2 2 , 3

 

a a a

 

3 ,

1 3 , 2 3 , 3

a a a

1

,

1 1

, 2 1

, 3 a a a a a a

      

2 , 2 2 , 3 2 ,

1 2 , 3 2 ,

1 2 , 2

Il suo determinante si calcola: det A a a a a a a

2 ,

1 2 , 2 2 , 3 1

,

1 1

, 2 1

, 3

a a a a a a

3 , 2 3 , 3 3 ,

1 3 , 3 3 ,

1 3 , 2

a a a

3 ,

1 3 , 2 3 , 3 7

Dall’analisi del problema si può facilmente dedurre che per Processi e algoritmi

risolvere il determinante di una matrice di ordine superiore a 2 sarà ricorsivi

necessario richiamare ricorsivamente la funzione per il calcolo del

determinante stesso. Infatti nello sviluppo ogni elemento della prima riga

viene moltiplicato con il suo minore complementare, ovvero il

determinante della matrice di un ordine inferiore ottenuta eliminando la Programmazione ricorsiva

prima riga e una delle colonne.

Nel programma da me creato in VisualBasic questa procedura è

rappresenta dalla seguente funzione:

Public Function Determinante(ByVal matrixA, dimensioneA,) As Long

If (dimensioneA > 2) Then 'risoluzione di matrici di ordini superiori a 2

Dim MatrixB() As Long 'matrice temporanea di 1 ordine inferiore a quella data

Dim dimensioneB As Long 'ordine della matrice temporanea

Dim ma As Long ‘complemento algebrico

Dim pos As Long 'posizione dell'elemento di sviluppo

Dim mtot As Long ‘somma dei prodotti del complemento algebrico per il minore complementare

dimensioneB = dimensioneA - 1

ReDim MatrixB(1 To dimensioneB, 1 To dimensioneB) As Long

Dim rB As Long 'contatore righe della matrice temporanea

Dim cB As Long 'contatore colonne della matrice temporanea

For i = 1 To dimensioneA 'per ogni elemento della 1a riga della matrice data

cB = 1

rB = 1

For ra = 1 To dimensioneA 'per ogni elemento riga della matrice data

For cA = 1 To dimensioneA 'per ogni colonna della matrice data

If (ra <> 1 And cA <> i) Then 'se la posizione NON equivale a una posizione nulla

MatrixB(rB, cB) = matrixA(ra, cA) 'composizione della matrice di 1 ordine inferiore

If (cB < dimensioneB) Then

cB = cB + 1 'contatore delle colonne della matrice temporanea

ElseIf (cB = dimensioneB) Then

cB = 1

rB = rB + 1 'contatore delle righe della matrice temporanea

End If

End If

Next cA

Next ra

pos = 1 + i 'posizione dell'elemento lungo il quale si sta sviluppando

ma = Determinante(MatrixB, dimensioneB) ‘richiamo ricorsivo alla funzione

If (pos Mod 2 = 0) Then '

ma = ma '

Else 'composizione del minimo algebrico

ma = -ma '

End If '

mtot = mtot + (ma * matrixA(1, i)) 'determinante della matrice data

Determinante = mtot

Next i

End If

If (dimensioneA = 2) Then 'risoluzione di matrici di ordine pari a 2

Determinante = (matrixA(1, 1) * matrixA(2, 2)) - (matrixA(1, 2) * matrixA(2, 1))

End If

If (dimensioneA = 1) Then 'risoluzione di matrici di ordine 1

Determinante = matrixA(1, 1)

End If

End Function 8

Un’altra procedura matematica che può essere semplicemente Processi e algoritmi

ridotta ad una funzione ricorsiva è quella per il calcolo del fattoriale di un ricorsivi

numero (n!) . Il fattoriale di un numero n si calcola infatti nel seguente

modo:  

     

      

• 

n

! n n 1 n 2 n n 1

che ricorsivamente può essere scritto: Programmazione ricorsiva

 

 

  

• n

! n n 1 !

Che nel programma da me scritto in Java si traduce nella

seguente funzione:

public long fatt (int n)

{ if(n > 0)

{ return n * fatt(n-1); //Richiamo ricorsivo alla funzione

}

else if(n == 0)

{ return 1; //Il fattoriale di 0 è per definizione uguale a 1

}

return 0;

}

L’ultimo programma da me realizzato e qui preso in esame

permette di disegnare e zoomare un numero indefinito di volte l’insieme

di Mandelbrot. Tale frattale è descritto da una funzione ricorsiva che,

preso un punto P sul piano dei numeri complessi, lo eleva al quadrato un

numero n di volte sommandolo ogni volta allo stesso punto P di partenza e

verificando per ogni iterazione se esso si allontani dall’origine o se esso

tenda a rimanere confinato in quello che viene detto cerchio critico

(circonferenza con centro nell’origine degli assi e di raggio pari a 2).

In questo caso il programma da me realizzato non fa uso di un

vero e proprio richiamo ricorsivo a una funzione, sfrutta invece un ciclo

che ad ogni iterazione eleva al quadrato il numero complesso ottenuto

dall’iterazione precedente (ciò che si ottiene è in ogni caso una funzione

ricorsiva del tipo f[f[f[…f[P]]]] ).

Public Sub calcola(a, b)

n = 0

az = 0 ‘parte reale del numero complesso P = a + bi

bz = 0 ‘parte immaginaria del numero complesso P = a + bi

tz = 0 ‘variabile temporanea utile a fini di calcolo

Do

tz = (az ^ 2) - (bz ^ 2) ‘

bz = 2 * az * bz ‘elevamento al quadrato

az = tz ‘

az = az + a ‘

bz = bz + b ‘Il nuovo punto è sommato a quello di partenza

n = n + 1 ‘numero di iterazioni

Loop Until (Sqr(az ^ 2 + bz ^ 2) > 2) Or (n > 100) ‘il ciclo ha termine quando il punto esce dal cerchio critico o quando esso vi rimane

‘perennemente confinato (vengono superate le 100 iterazioni)

If n < 100 Then

n = n Mod 50