Newsgroup: it.comp.lang.c++
Titolo: Iterazione e Ricorsione

ciao a  tutti.
scusate la mia ignoranza, ma c'è qualcuno che mi spieghi il passaggio tra i
due cicli iterativo e ricorsivo?
lo so, sono le basi.. ma ho appena iniziato!
grazie mille per le risposte
--
§ÜPeR|\|ØV@
http://oasisitalia.freeweb.org
OasisItalia
Il Miglior Punto Di Riferimento Italiano Sugli Oasis

due cicli iterativo e ricorsivo?
Spero che applicherai questi principi a Windows.
Una iterazione e' l' esecuzione ciclica di un gruppo di istruzioni.
Una ricorsione e' l'esecuzione nidificata di uno stesso gruppo di
istruzioni.
Ad esempio :
// iterazione
int it_fact( int n ) 
{
    int p = 1, i ;
    for ( i = 1 ; i <= n ; i++ )
        p *= i ;
    return p ;
}
// ricorsione
int rc_fact( int n ) 
{
    return ( n ) ? n * it_fact( n - 1 ) : 1 ;
}
--
Andrea Laforgia (
andrea_...@bigfoot.com
)
--------------------------------------------------------------
"Partire e' un po' morire e morire e' partire un po' troppo !"
--------------------------------------------------------------

}
scusa :
// ricorsione
int rc_fact( int n ) 
{
    return ( n ) ? n * rc_fact( n - 1 ) : 1 ;


 grazie mille per le risposte
Hai appena iniziato e ti occupi di come passare da un ciclo iterativo
a uno ricorsivo...?  Mah -- mi sembra un caso di "correre prima che
camminare", comunque, contento tu...
Il passaggio da un ciclo iterativo a uno recursivo e` sempre
assai agevole:
    // ... codice precedente al ciclo ...
    while(condizione) {
        corpodelciclo;
    }
    // ... codice successivo al ciclo ...
al netto dello scoping delle variabili visibili in "corpodelciclo"
(problema che si puo` "parare" ad esempio con passaggio di parametri,
nel caso generale by-reference), diventa:
    void funzionerecursiva() {
        if(condizione) {
            corpodelciclo;
            funzionerecursiva();
        }
    }
e al punto di chiamata:
    // ... codice precedente al ciclo ...
    funzionerecursiva();
    // ... codice successivo al ciclo ...
Vari costrutti C (e C++) che violano la "forma normale" while() del
ciclo si traducono molto agevolmente nel passaggio da ciclo iterativo
a ciclo recursivo.  Ad esempio, se "corpodelciclo" contiene un "break"
nella forma iterativa, questo diviene "return" nella forma recursiva.
Il passaggio inverso, da recursivo a iterativo, puo` richiedere
la introduzione di un esplicito stack se la forma recursiva del
ciclo contiene variabili automatici (parametri inclusi).  Se la
recursione e` multipla o indiretta, il passaggio da recursivo a
iterativo diventa ancora meno agevole: puo` essere necessario
operare (almeno un passaggio intermedio!) in termini di un altro
stack (di "punti di ritorno") ed espliciti "goto calcolati" (in
C++, questi si esprimono tipicamente come switch).
L'operazione, non necessariamente semplice!, di passaggio da ciclo
recursivo a ciclo iterativo e` nota come "eliminazione della
recursione" e puo` anche essere fatta _parzialmente_: ad esempio,
la *recursione in coda*, cioe` il caso particolare in cui la
chiamata recursiva e` l'ultima istruzione eseguita dalla funzione
recursiva, si "dipana" in un while senza troppi problemi, e a
volte puo` bastare l'intervento a questo solo livello.
Un altro approccio molto spesso utile per eliminare molti dei
costi della recursione con poca o nessuna fatica e` quello di
introdurre una *mappa di cache dei risultati* ("memoizing" e`
il nome generale della tecnica in questione).  Questo e`
particolarmente utile per funzioni pure, matematicamente
_definite_ in modo recursivo, e puo` risultare anche piu`
importante da un punto di vista prestazionale rispetto alla
eliminazione vera e propria della recursione.
Si consideri ad esempio il classico caso del fattoriale:
    myverylongint fatt1(myverylongint n) {
        if(n<=0) return 1;
        else return n*fatt1(n-1);
    }
Non si tratta esattamente di tail-recursion perche` la
moltiplicazione per n deve avvenire DOPO il ritorno della
chiamata recursiva.  Nondimeno, ci siamo vicini, e quindi
l'eliminazione non sarebbe poi difficile:
    myverylongint fatt2(myverylongint n) {
        myverylongint result=1;
        while(n>0) {
            result *= n;
            --n;
        }
    }
Ma se il programma calcola moltissimi fattoriali, questo
approccio richiede comunque una enorme quantita` di
moltiplicazioni di oggetti myverylongint.  Con un
classico scambio spazio/tempo, possiamo a volte fare
dei veri miracoli...:
    myverylongint fatt3(myverylongint n) {
        static std::map<myverylongint,myverylongint> memo;
        if(n<=1) return 1;
        if(memo.find(n)==memo.end()) {
            memo[n] = n*fatt3(n-1);
        }
        return memo[n];
    }
Qui abbiamo ripreso, internamente, la forma recursiva,
ma la recursione e` usata "poche volte", nel corso, solo,
dell'iniziale "popolamento" della mappa "memo"; il costo
di spazio puo` essere sostanziale, ma il numero (nel senso
ammortizzato) di operazioni aritmetiche e` ora veramente
minimale.
Naturalmente, in un caso particolare come questo, si puo`
anche (e proficuamente) fare il memoizing usando uno
std::vector invece della generale std::map; e popolare
il memo con un ciclo iterativo invece di quello recursivo.
Ma l'approccio recursione+memoizing e` piu` generale e
spesso piu` rapido in termini di implementazione.
Alex