Newsgroup: it.comp.lang.c++
Titolo: Aiuto per metodo di conversione

Qualcuno mi puo' suggerire un buon metodo per convertire un
sottoprogramma o un blocco di codice dalla forma iterativa a quella
ricorsiva e viceversa?
E' per un esame di Fondamenti di Informatica.
Grazie.
Carmine

ricorsiva e viceversa?
E` piuttosto semplice.  Per trasformare una chiamata recursiva
in una iterazione, nel caso generale, introduci uno stack nel quale
registrare tutte le variabili locali della funzione (compresa la
informazione equivalente al "program counter"); sostituisci la
chiamata recursiva in, push di tutto lo stato locale e goto ad una
label all'inizio della funzione; sostituisci i return in, se lo stack in
questione non e` vuoto, pop dello stato locale e goto a una label
subito dopo il punto di chiamata.  Ulteriori semplificazioni, come
trasformare i goto in schemi piu` strutturati e non salvare sullo
stack cio` che non serve, sono opzionali e non c'entrano con la
trasformazione recursione->iterazione in quanto tale.
La trasformazione inversa e` piu` semplice, ma solo se la
iterazione riguarda una intera funzione (perche` non puoi fare
vere e proprie chiamate, recursive o meno, a un blocco che
non sia una funzione).  Specificamente, un'iterazione del tipo
fondamentale:
        void pippo(argomenti)
        {
            do {
                qualcosa
             } while(condizione);
        }
diventa, trivialmente:
        void pippo(argomenti) {
            qualcosa;
            if(condizione) pippo(argomenti);
        }
("tail recursion", ovvero recursione "in coda").
Vediamo un esempio di eliminazione di recursione.
L'implementazione recursiva triviale del fattoriale:
        int factorial(int n) {
            if(n<2) return 1;
            else return n*factorial(n-1);
        }
Qui la chiamata recursiva e` entro una espressione
e ci sono due return, quindi ci semplifichiamo la vita
anzitutto riscrivendo:
        int fact1(int n) {
            int result = 1;
            if(n>=2) {
                result = fact1(n-1);
                result *= n;
            }
            return result;
        }
Lo "stato locale" si compone di due interi, result e n,
quindi introduciamo uno stack ausiliario, in standard
C++ implementandolo ad esempio come lista:
        int fact2(int n) {
            std::list<pair<int,int> > stack;
            int result;
        inizio:
                result = 1;
                if(n > 1) {
                    stack.push_back(make_pair(result,n));
                    n = n-1;
                    goto inizio;
        ritorno:
                    result *= n;
                }
                if(stack.empty()) return result;
                pair rn = stack.back();
                stack.pop_back();
                result = rn.first;
                n = rn.second;
                goto ritorno;
        }
Il C++ probabilmente protestera` per il "goto ritorno",
che salta il mezzo ad un blocco; notiamo che possiamo
eliminarlo sdoppiando il blocco stesso:
        inizio:
                result = 1;
                if(n > 1) {
                    stack.push_back(make_pair(result,n));
                    n = n-1;
                    goto inizio;
                }
        ritorno:
                if(n > 1) {
                    result *= n;
                }
L'eliminazione della recorsione e` cosi` completa, ma
per pulizia possiamo semplificare assai il codice che
ne risulta (solo perche` siamo fortunati e "factorial" ha
una struttura intrinseca molto semplice...!).  Specificamente,
il blocco dalla label inizio inclusa a quella ritorno esclusa,
ripetiamolo per chiarezza:
        inizio:
                result = 1;
                if(n > 1) {
                    stack.push_back(make_pair(result,n));
                    n = n-1;
                    goto inizio;
                }
ha chiaramente la struttura di un ciclo while; inoltre
in questo ciclo non pushiamo sullo stack altro che "1"
come valore di result (primo elemento della coppia),
quindi possiamo risparmiarci questo e scrivere
        int fact3(int n) {
            std::list<int> stack;
            int result = 1;
            while(n>1) {
                 stack.push_back(n);
                 n = n-1;
            }
Qui, all'uscita dal loop "while(n>1)", possiamo asserire
con tranquillita` che n<=1, quindi la prima moltiplicazione
non avviene, e possiamo semplificare il secondo loop:
        ritorno:
                if(stack.empty()) return result;
                n = stack.back();
                stack.pop_back();
                result *= n;
                goto ritorno;
ma anche questo ha una struttura di while, quindi lo
riscriviamo:
        while(!stack.empty()) {
                n = stack.back();
                stack.pop_back();
                result *= n;
        }
        return result;       
Ecco finalmente rivelata come iterazione la vera
struttura della nostra iniziale funzione recursiva:
una prima fase in cui si mettono in stack (esplicito
adesso, implicito nella recursione) i numeri da 2
a n incluso; una seconda fase in cui si vuota lo
stack moltiplicando tutti i numeri che contiene.
Per questo tipo di recursioni intrinsecamente lineari,
una buona alternativa e` di applicare prima la classica
ottimizzazione che trasforma la recursione nella forma
"tail recursion", poi eliminare quest'ultima in un singolo
ciclo while.  Ma e` un approccio meno generale, in
quanto non tutte le recursioni si possono mettere nella
forma "in coda"!
Alex