Trasformazioni Ricorsive Iterative

[Goldrake_xyz]

COME TRASFORMARE UNA PROCEDURA RICORSIVA IN UNA PROCEDURA ITERATIVA :
====================================================================

La Trasformazione di una procedura ricorsiva in una procedura iterativa
prevede l'uso di una pila di tipo LIFO e di due funzioni : push e pop.
push - inserisce un campo di variabili nella pila.
pop - restituisce il campo di variabili dalla pila.

il campo di variabili consiste in :

una parte per le variabili da ripristinare al rientro,
una parte che contiene l'indirizzo di rientro dalla ricorsione.

La pila LIFO significa Last In First Out cio‚ (in ordine di tempo)
l'ultimo campo entrato è il primo ad uscire.

Notare che la normale ricorsione procede prima in profondità,
cioè procede con il DEPTH-FIRST e questo modo di procedere mette al massimo
tanti elementi nella pila, quanto massima ‚ la profondità di ricorsione.
(generalmente pila molto piccola=poco spreco di memoria)

----------------------------------------------------------------------------


esempio di una procedura ricorsiva :


procedura xxx (int a,b,c)
var q1,q2,q3;
[prima ist.exe ]
[ prg.p1 ]
[ ]
xxx(1+q1,q2,q3);
[uso tutte var ]
[ prg.p2 ]
[ ]
end;


La chiamata ricorsiva quindi si deve trasformare nel seg. modo

Primo : si salvano le variabili che dal punto della ricorsione
in poi vengono effettivamente utilizzate.
(Ripristino successivo delle variabili)
si memorizza il punto di ritorno (vedi punto Quarto).
es: push(a,b,c,q1,q2,q3,Label1);

Secondo : si trasformano i parametri della chiamata ricorsiva
in quelli nell' intestazione del programma, eseguendo
le opportune operazioni se necessario.
es: a=1+q1; b=q2; c=q3;

Terzo : si effettua un salto incondizionato alla prima
istruzione eseguibile della procedura.
es: goto start;

Quarto : si crea una Label per permettere il rientro dalla ricorsione.
es: Label1:

La fine della procedura va modificata aggiungendo la funzione di
recupero, cio‚ di ritorno dalla ricorsione.
es: if (not pilavuota) { pop(a,b,c,q1,q2,q3,Labelx); goto Labelx; }

a trasformazione avvenuta la procedura sarà :

procedura xxx (int a,b,c)
var q1,q2,q3,Labelx;
start:
[prima istr. eseguibile ]
[ prg.p1 ]
[ ]
push(a,b,c,q1,q2,q3,Label1); /* passo 1 */
a=1+q1; b=q2; c=q3; /* passo 2 */
goto start; /* passo 3 */
Label1: /* passo 4 */
[ uso di a,b,c,q1,q2,q3 ]
[ ]
[ ]
if (not pilavuota)
{ pop(a,b,c,q1,q2,q3,Labelx);
if (Labelx==Label1) goto Label1;
}
end;


NOTA :

I - in teoria si dovrebbero salvare (push) tutti i parametri locali
della procedura, cioè sia i parametri dichiarati in intestazione
di programma, sia le variabili dichiarate nella procedura,
MA ...
se dopo la chiamata ricorsiva presa in considerazione
la variabile non è utilizzata, allora è inutile salvarla nella
pila, perchè non serve ripristinare il suo valore , che
in ogni caso non verrà utilizzato !

Questo consente di risparmiare spazio in memoria, creando
una pila, se possibile con meno campi di quelli necessari
per salvare tutte le variabili locali.

II - La procedura PUSH dovrebbe effettuare anche un controllo sulla
grandezza della pila per non eccedere la capacità di memoria
dell' elaboratore.
La funzione POP è conveniente che ridia come valore proprio
un BOOLEAN (TRUE=elementi nella pila, FALSE=pila vuota)
così da scrivere if POP(.....) then ....

Cordiali Saluti.:)

Copyright by Zimba Zomba

(Zimba Zomba = famoso genio informatico che viveva in uno
sperduto villaggio situato sulle rive del fiume bramaputra)


P.S. sono molto apprezzati suggerimenti e/o correzzioni, Grazie !

[McK]

Mi sembra ok. Solo una cosa, io la procedura ricorsiva la sostituirei con una che fa veramente qualcosa, tipo il fattoriale. In questo modo riesci a fare un esempio che ti rimanda un risultato che tutti possono toccare con mano! :)
Per il resto mi sembra una bella spiegazione, mi ricorda il primo anno di ingegneria informatica! :D

McK

[Goldrake_xyz]

ok eccone un' altra ...


IMPLEMENTAZIONE DELLA RICORSIONE BREADTH FIRST
=============================================

La ricorsione BREADTH-FIRST ‚ purtroppo non è implementata
nei linguaggi come il C e il PASCAL, allora l'unico modo per
renderla effettiva è la trasformazione da Ricorsione BREADTH-FIRST
ad un programma iterativo BREADTH-FIRST

Sia la ricorsione DEPTH-FIRST che la BREADTH-FIRST hanno lo
stesso numero di nodi e la stessa disposizione.
Ma cambia il modo di attraversamento dell' albero ricorsivo.

(Quindi in generale non sono la stessa cosa, anche se talvolta
il programma in depth-first può essere convertito in breadth-first
ed ottenere lo stesso risultato (il modo di costruzione è però diverso))

La ricorsione BREADTH-FIRST funziona così :
prima si esegue tutta la procedura ricorsiva ignorando le chiamate
ricorsive presenti, poi terminata tutta la procedura si esegue
quella che era la prima chiamata ricorsiva , poi la seconda chamata
ricorsiva e così via.
così facendo si procede a strati, cioè vengono eseguiti prima tutti
i nodi di uno stesso livello poi tutti i nodi del livello successivo.

La ricorsine BREADTH-FIRST la posso ottenere, scrivendo un programma
ricorsivo immaginario e poi eseguire una trasformazione ricorsivo-iterativa
secondo le regole del BREADTH-FIRST e mettere quest' ultima sul calcolatore.
------------------------------------------------------------------------------------------------------------------

il programma immaginario di una ricorsione BREADTH-FIRST è uguale
nell' aspetto ad un programma ricorsivo DEPTH-FIRST :

esempio di una procedura ricorsiva :


procedura xxx (int a,b,c)
var q1,q2,q3;
[prima ist.exe ]
[ prg.p1 ]
[ ]
xxx(1+q1,q2,q3);
[uso tutte var ]
[ prg.p2 ]
[ ]
end;


LA TRASFORMAZIONE RICORSIVO-ITERATIVA si effettua così :

Innanzittutto si devono creare due funzioni :

PUSH - immette nella pila FIFO un campo di dati;
POP - preleva dalla pila FIFO un campo di dati;

il campo di dati è composto da variabili da salvare , tanti campi
per quante sono le variabili da passare durante la chiamata ricorsiva.
(Quì non esiste il campo dell'indirizzo di ritorno)
la pila è di tipo FIFO = First In First Out (in ordine di tempo)
e significa : il primo campo entrato è il primo campo ad uscire
cioè i dati si mettono da un lato, ma si prelevano dal lato opposto.
La trasformazione ricorsivo-iterativa BREADTH-FIRST è più semplice
della trasformazione ricorsivo-iterativa normale.

************

la chiamata alla funzione si trasforma nel seguente modo :

la chiamata ricorsiva và sostituita con un PUSH(.....)
i parametri salvati dal push devono essere gli stessi della
chiamata ricorsiva nè più nè meno.

la prima istruzione eseguibile della procedura deve essere etichettata.

dopo l'ulitma istruzione va messa la parte di riesumazione delle
variabili (pop) e poi la trasformazione parametri di chiamata
in parametri di intestazione procedura
(si potrebbe più brevemente riesumare tali parametri direttamente
con il nome di intestazione messo nella procedura.
Nel programma sotto è stato fatto appunto così).

il programma diverrebbe allora :


procedura xxx (int a,b,c)
var q1,q2,q3;
Start:;
[prima ist.exe ]
[ prg.p1 ]
[ ]
push(1+q1,q2,q3);
[uso tutte var ]
[ prg.p2 ]
[ ]
if (not pilavuota)
{ pop(a,b,c);
goto Start;
}
end;

ATTENZIONE: questo modo di funzionamento (breadth-first) implica
che la pila sia costretta a salvare tutte le variabili di un
livello ricorsivo, prima di passare al livello ricorsivo superiore.
Quindi la pila cresce esponenzialmente e di conseguenza si ha
bisogno di grandi quantità di memoria.
Esempio:

ricorsione breadth-first a 2 chiamate

profondità massima di ricorsione valida = 9

es:
inizio con n=1;

if (n < 10) then { call ricorsione1(n+1,...);
call ricorsione2(n+1,...); }


allora il livello 9 avrà 2^9 memorizzazioni nella pila
(livello 1 = 2^1 memorizzazioni in pila (cio‚ 2 push())
se ogni memorizzazione richiede 8 byte allora servirebbero
4096byte = 4K solo per la pila nell' ultimo livello ricorsivo.
continuando, il livello ricorsivo 10 effettua il blocco ricorsivo
e quindi non viene effettuato alcun push.

********************

RIDUZIONE PILA :

Allora si può considerare il livello ricorsivo 10 come un livello
ininfluente poichè quel livello ha il solo scopo di bloccare
un ulteriore approfondimento della ricorsione.

Allora perchè bisogna eseguire per esso una memorizzazione delle
variabili con i push al livello 9 ?

In effetti si potrebbe eliminare nel caso appena esposto
la clausola del blocco ricorsivo generale, e mettere invece un
blocco ricorsivo in modo da eliminare i push del livello 9.

es : if(n<8) push(n+1,...)

Qundi si può in questo caso bloccare tutti i push al livello N-1,
dove N ‚ l'ulimo livello valido.

così facendo non si è costretti a memorizzare l'ultimo livello
della ricorsione che è anche quello più dispendioso in termini
di memoria.

Sfortunatamente non è un metodo generale di riduzione, in quanto
non sempre si può sapere quando si è arrivati al livello N-1.

**************
N.B. La procedura PUSH dovrebbe effettuare anche un controllo sulla
grandezza della pila per non eccedere la capacità di memoria.

La funzione POP ‚ conveniente che ridia come valore proprio
un BOOLEAN (TRUE=elementi nella pila, FALSE=pila vuota)
così da scrivere if POP(.....) then ....


Cordiali Saluti. :)

Copyright by Zomba Zimba

Allegati alcuni esempi in C da riadattare alla grafica corrente.

[cionci]

Nno ho capito...sarebbe una domanda o un consiglio ?

[Goldrake_xyz]

Mah, è un' utilità :) se qualche programmatore vuole divertirsi
con la ricorsione breadth first quì ho scritto qualche trucco.
e se si vuole ho aggiunto anche dei piccoli programmi in
C per vedere come funziona il tutto.

(x i programmi in C bisogna riadattare i comandi grafici
al compilatore che si ha disponibile.)


Coriali Saluti.:)

[mmx[ngg]]

Un pò contorto ma è interessante...mi fai ricordare uno studio ke avevo fatto un paio di anni fà. La proposta di un professore era di scrivere un merge sort senza usare la ricorsione...potresti provare a implementare quello come esempio :)

Se riesco a trovare quello ke avevo fatto io lo posto.

Cmq tieni presente ke la ricorsione è utilizzata per scriver codice kiaro ed efficente...quindi se si cerca di non usarla si deve cmq ottenere lo stesso risultato ;)

[Goldrake_xyz]

Originariamente inviato da mmx[ngg]
Cmq tieni presente ke la ricorsione è utilizzata per scriver codice kiaro ed efficente...quindi se si cerca di non usarla si deve cmq ottenere lo stesso risultato ;)

Si, concordo al 100% __:)

Effettivamente questa discussione nasce da alcune considerazioni
che avevo fatto ai tempi dei primi anni di Univeritè,
Avevo notato che su libri di illustri prof. Italiani ... di cui
ovviamente non posso fare il nome, erano scritte alcune
imprecisioni , chiamiamole così, riguardo i meccanismi Ricorsivi.
Effettivamente quanto scritto su quei libri era frutto della
copia della copia della copia di qualche altro libro magari scritto
in inglese....
E come si sà dopo molti passaggi qualcosa si perde ....
e qualcosa si aggiunge di fantasia .... :)

Le regole esposte nella trsformazione ricorsivo iterativa
sono generali e possono essere applicate a qualunque
programma.
Principalmente servono per capire come funziona il meccanismo
della ricorsione, quindi sono indirizzate principalmente a tutti
gli studenti dei primi anni di Ing. informatica.

Le regole esposte per la trasformazione ricorsivo Breadth-First
sono invece da applicare se si vuole una ricorsione che
procede a strati, e che non è implementata su nessun linguaggio.
(a quanto nè so io)
E quindi l'unico modo x ottenerla è passare attraverso una
trasformazione iterativa.

Se hai tempo scarica i 3 programmi in C ,
che contengono un'immagine grafica ricorsiva in 3D
sviluppati nei 3 modi proposti.
Il Primo è ricorsivo semplice .
Il Secondo è trasformato in iterativo .
Il Terzo è trasformato in iterativo Breadth-First
(P.S. Le istruzioni grafiche sono da riadattare al compilatore
in uso, in quanto i programmi furono scritti per il Turbo C2.0)

Salutissimi..:)

[misterx]

Originariamente inviato da Goldrake_xyz

Principalmente servono per capire come funziona il meccanismo
della ricorsione, quindi sono indirizzate principalmente a tutti
gli studenti dei primi anni di Ing. informatica.




ti prendo in parola e ti chiedo secondo te come si evolve o propaga una ricorsione multipla:)

esempio:
http://www.mokabyte.it/2003/03/ricorsione.htm

[Goldrake_xyz]

La ricorsione multipla si evolve ad albero binario, ternario, ecc,
a seconda del numero di chiamate ....
ma la "meccanica" è la stessa della ricorsione semplice.
se vedi i 3 programmi che ho messo sul link c'è appunto
una ricorsione multipla (3 chiamate alla funzione frattale)__ :)

Ho visitato il link ... è veramente ben fatto, e dice ....

Difatti anche un metodo ricorsivo viene trasformato in sequenziale dall'interprete attraverso il runtime-stack durante la fase di esecuzione.


Right al 100 %

Cordialmente. :)

[misterx]

Originariamente inviato da Goldrake_xyz
La ricorsione multipla si evolve ad albero binario, ternario, ecc,
a seconda del numero di chiamate ....
ma la "meccanica" è la stessa della ricorsione semplice.
se vedi i 3 programmi che ho messo sul link c'è appunto
una ricorsione multipla (3 chiamate alla funzione frattale)__ :)

Ho visitato il link ... è veramente ben fatto, e dice ....


Right al 100 %

Cordialmente. :)


disegnare un albero con due variabili non mi pare molto banale


esempio:

F(a,b) = F(a,b)+b*F(a,b)

[Goldrake_xyz]

Si, effettivamente dipende dalla profondità del livello ricorsivo:
La funzione ricorsiva che hai scritto : F(a,b) = F(a,b)+b*F(a,b)
è un albero binario, infatti le chiamate ricorsive della
funzione F(a,b) sono 2.
ma così come è scritta ha una profondità infinita,
in quanto manca la clausola di terminazione della ricorsione.

Effettivamente avevo un piccolo programma per disegnare
i nodi relativi agli alberi ricorsivi ... (solo di tipo binario però)
se lo ritrovo lo scrivo sul forum, sono poche righe.


Saluti.:)

[misterx]

pardon!

correggo subito :)

F(a,b) = F(a-1,b-1)+b*F(a-1,b)

[Goldrake_xyz]

Per creare l'albero binario basta fare :


F(a,b) = F(a-1,b-1) + b*F(a-1,b)
/ \
F(a,b) = F(a-1,b-1) + b*F(a-1,b) F(a,b) = F(a-1,b-1) + b*F(a-1,b)
/ \ / \




e così via fino al blocco ricorsivo che sarà del tipo
(per la variabile a positiva)

If (a<=0) return 0 ;

Saluti.

[Goldrake_xyz]

Bene, Sabato ho scaricato il compiler LCC WIN32
e ho riscritto il programma....
Lo stile di programmazione è orribile ma ho avuto solo
un giorno per fare il tutto.
Allegato al sorgente c'è anche il BITMAP del disegno
che dovrebbe apparire....... :cincin: