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

  Quando conviene usare l'iterazione e quando la ricorsione???
Tnk
-- 
Kleidemos
C++ Programmer
kleidemo...@altervista.org
http://kleidemos.altervista.org/

>   Quando conviene usare l'iterazione e quando la ricorsione???
Quando conviene ;-)  A parte gli scherzi, ci sono algoritmi per i
quali č preferibile la versione ricorsiva, per il semplice fatto che č
piů vicina al ragionamento logico che gli sta dietro.  Ad esempio, per
implementare la visita di un albero, a me viene piů semplice ragionare
in termini ricorsivi (visto che l'albero stesso ha una struttura
definibile in termini ricorsivi).  Qualsiasi algoritmo ricorsivo puň
essere trasformato in algoritmo iterativo e viceversa, ma, ad esempio,
č un massacro, dal punto di vista prestazionale, eseguire il calcolo
del fattoriale mediante un algoritmo ricorsivo.
Molto meglio usare un algoritmo iterativo.

   Quando conviene usare l'iterazione e quando la ricorsione???
Su un noto libro di C++ si trova come suttotitolo
di un capitolo: "iterativo č umano, ricorsivo č divino".
La risposta č: dipende.
:-)
SiMoStro

 :-)
Da cosa??


 Molto meglio usare un algoritmo iterativo.
Scusami, se ben ricordo a FDI mi dissero che
la ricorsione per il fattoriale non era un disastro,
mentre lo era la per la serie di Fibonacci... ricordo male?

 mentre lo era la per la serie di Fibonacci... ricordo male?
In effetti il mio xp2600+ nn arrivava alle 50 iterazioni di Fibonacci ed era
occupato al 100 %



Premesso che dipende tutto da quale algoritmo ricorsivo/iterativo
uno implementa, ricordi bene.
Diciamo che una implementazione ricorsiva-scema ed una
iterativa-scema del fattoriale hanno grosso modo lo stesso costo:
double ricfac(int n)
{
   return (n<=1 ? 1.0 : n*ricfac(n-1));
}
double itefac(int n)
{
   double f=1.0;
   while (n>=2) {f*=n; n--;}
   return f;
}
Quella iterativa non da problemi, e nemmeno quella ricorsiva, in quanto
ad ogni chiamata ho 1 chiamata ricorsiva. Alla fine avro' chiamato
grosso modo n volte la funzione ricorsiva.
Se invece uno implementa in modo scemo-ricorsivo la funzione di Fibonacci
ovvero
f(1)=f(0)=1
e f(n)=f(n-1)+f(n-2) per n>1,
allora ogni chiamata ricorsiva invochera' 2 volte se stessa.
Questo fa si che, grosso modo, il numero di chiamate da fare
e' proporzionale al numero di Fibonacci che si vuole calcolare,
quindi esponenziale.
Viceversa, un metodo iterativo che si mantiene in memoria gli
ultimi 2 valori calcolati esegue un numero di iterazioni
proporzionale a n, quindi e' assolutamente preferibile.
In realta' per calcolare il fattoriale di numeri grossi
si usa una tecnica mista: una tabella per i numeri piccoli
piu' una tecnica ricorsiva basata su formule che in
realta' dimezzano circa l'argomento
(es:
F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k
F[2k-1] =   F[k]^2 + F[k-1]^2
F[2k] = F[2k+1] - F[2k-1]
come usate da gmp.)
Ciao,
g.

 di un capitolo: "iterativo è umano, ricorsivo è divino".
Ricorsivo può essere diabolico se si hanno vincoli sulla dimensione dello
stack (vd., tipicamente, programmazione real time embedded)

 :-)
beh, questa mi pare una cavolata!
Tommy

 del fattoriale mediante un algoritmo ricorsivo.
Volevi forse dire Fibonacci.... Ma il massacro a volte non e' solo
prestazionale... a volte e' semplicemente inaffrontabile farlo!
Tommy

 Tommy
Argomenta :)


 beh, questa mi pare una cavolata!
Il mondo mi piace perché su certe cose
la si può pensare diversamente.
SiMoStro

 di Fibonacci ed era occupato al 100 %
Non capisco se ti stai riferendo alla versione iterativa o ricorsiva.
"In effetti" mi fa pensare a quella ricorsiva, si diceva che quella era
lenta....
"iterazioni" mi fa pensare alla versione iterativa...
il fatto che non hai ottenuto nessun risultato mi fa nuovamente pensare
a quella ricorsiva....
Allora, ci hai confusi! A quale ti riferivi? Alla ricorsiva, vero?
"non arriva" in che senso?
Nel senso che dovresti aspettare troppo a lungo?
... pero' prima o poi "arriva" a darti una soluzione ;-)
Beh, e' normale che ci metta molto. Per Fibonacci(25) il programma deve
fare 242,785 chiamate ricorsive!
Tra le altre cose, e questo aggrava, molte di queste sono inutili
(calcola le stesse cose piu' volte!)
Una versione iterativa puo' invece facilmente ritornarti anche il
fibonacci di 5000 in meno di mezzo secondo, sulla tua macchina, che per
la cronaca e':
+387896845438832563370191630832590531208212771464624510616059721489555013904
4037097010822916462210669479293452858882973813483102008954982940361430156911
4789383642165639441069102145056341337065586562382546567007125259299038549338
1392883637834751890876297071203333705292310769300851809384980180384781399674
8881765554653788291644268912980384613778969021502293082475666346224923071883
3248032803750391303529033045058427011476352422702109346376991040067141748832
9842289149127310405432875329804427367682297724498774987455569190770388063704
6832794811358973739993110106219308149018570815397854379195305617510761053075
6887837660336673554452588448862416192105534574936758978490279882343510235998
4466393485325641195222185956306047536464547076033090242080638258492915645287
6291575759142343809142302917491088984155209854432486594079793571316841692868
0395453095453886981146650820668628974206393234384884652409887423958738019769
9382031717420893226546887936400263079778005875912967138963421425257911687275
5600360311370547754724604639987588046985178408674382863125
;-)
Tommy

 Da cosa??
Se fossi io a porre una domanda del genere e l'interloquito
mi rispondesse con la pretesa di essere esaustivo, sentirei
puzza di presunzione... ;-)
Non posso risponderti in senso "assoluto", anzitutto perché
non sono un "programmatore a manetta" e secondariamente perché
penso bisognerebbe valutare la situazione.
Dipende da tante cose: Davide ha giustamente ricordato i sistemi
embedded per la dimensione dello stack, ma dipende anche dal S.O.,
le politiche di gestione delle risorse e di come l'applicazione è
"immersa" nelle altre applicazioni del sistema (pensa all'SRP di
Baker...);
potrebbero essere critiche le prestazioni: un'iterazione potrebbe
giovarsi di cicli semplici che si appoggiano sui registri, la ricorsione
necessita di accessi alla memoria per salvare le variabili della chiamata
alla procedura; viceversa, se l'algoritmo è complesso e richiede molte
variabili, l'iterazione potrebbe risultare pesante mentre la ricorsione
potrebbe invece risolvere semplicemente ed elegantemente il problema.
Non posso che ribadire il mio "dipende".
SiMoStro

 Argomenta :)
(ah....le solite frasi di Kleidemos.... :-( )
La ricorsione puo' essere a volte molto piu' elegante della iterazione
ed a volte molto meno.
Quando e' piu' elegante puo' essere "divina" quando non lo e' molto meno
"divina".
Quando e' elegante ma come nel caso di Fibonacci causa disastri e' molto
"umana", altro che "divina"!
Questo e' quello che penso.
Tommy
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

>> di un capitolo: "iterativo è umano, ricorsivo è divino".#
questa mi pare una cavolata!
Non hai quotato abbastanza.... fai sembrare che io risponda alla tua
affermazione e non a quella del libro.
Secondo me la cavolata e' quella del libro. Capisco cosa intenda... ma
*esagera*! Le motivazioni le trovi in risposta al messaggio di
kleidemos.


 Allora, ci hai confusi! A quale ti riferivi? Alla ricorsiva, vero?
ricorsiva :)



Che hanno di male???


 (calcola le stesse cose piu' volte!)
Scusate, ma per i numeri di Fibonacci ne' iterazione ne' ricursione
sono adatte...  ci vuole una state machine.  Il codice seguente e'
gia' stato postato piu' volte su questo gruppo...
#include <iostream>
#include <algorithm>
class fibo {
private:
  unsigned long penultimo;
  unsigned long ultimo;
public:
  fibo() : penultimo(0), ultimo(0) {}
  unsigned long operator()() {
    unsigned long questo = ultimo ? ultimo + penultimo : 1;
    penultimo = ultimo;
    return ultimo = questo;
  }
};
int main() {
  const unsigned int number(10);
  std::cout << "I primi " << number << " numeri di Fibonacci sono: ";
  std::generate_n(std::ostream_iterator<unsigned long>(std::cout, " "),
                  number, fibo());
  std::cout << std::endl;
}
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Dept. of Physics, Univ. of Padova, Italy              ROT13: 
ybe...@cq.vasa.vg

 }
Tommy

 *esagera*!
Era il "sottotitolo" di un capitolo, va letta
in quel contesto. Per la precisione il libro č:
----------------------------------------
Bjarne Stroustrup - "Il linguaggio C++"
cap. 5, Funzioni e file
     "L'iterazione č umana,
      la ricorsione divina."
                     L. Peter Deutsch
----------------------------------------
A parte le personali convinzioni, direi che
le fonti sono piuttosto autorevoli, non credi?
;-)
SiMoStro

 ;-)
si, non condivido la frase ma le fonti sono autorevoli ;-)
E' vero sul mio c'e' scritto:
"To iterate is human, to recurse divine" .
Tommy

 ed a volte molto meno.
Appunto: "dipende".

 secondo:
Be', considerando che il 5000-esimo numero di Fibonacci vale circa
3.8789684543883256337019163083259 * 10^(1044), quindi il tuo
fib(5000) era un numero praticamente casuale.
Il massimo numero di Fibonacci che sta in un intero di 32 bit (unsigned) 
e' il 47-esimo (ovvero 2971215073) quindi
in realta' il modo piu' veloce per calcolare i numeri di Fibonacci
rappresentabili su interi e' quello di precalcolarli e  memorizzarli in
una tabellina :-)
ciao,
g.

 gia' stato postato piu' volte su questo gruppo...
Mi sembra che programma il "state machine" rientri pienamente
nell'approccio iterativo.
Ad ogni iterazione si genera un nuovo numero di Fibonacci.
Non darei una definizione cosi' stretta di "approccio iterativo",
al punto di impedirgli di memorizzare variabili temporanee di
supporto,
ciao,
g.

 una tabellina :-)
Si, ovvio ma non se ti serve un solo numero. 
Se ti serve fib(5000) e poi fib(300) e poi fib(8000) etc... si....
Ma solo per un numero solo non serve a nulla e la mia funzione lo avevo
scritto con questo in mente.


 iterativa-scema del fattoriale hanno grosso modo lo stesso costo:
Piu' esattamente il loro costo e' in entrambe i casi proporzionale a
n. A parita' di costo tendenziale la versione ricorsiva puo' costare
molto di piu', perche' il costo di una chiamata di funzione e' di
qualche ordine di grandezza piu' alto di quello di un
incremento/decremento. Se pero' il compilatore ottimizza come si deve
il problema non si pone.
[cut del ragionamento corretto sul calcolo dei numeri di Fibonacci]
In generale e' opportuno distinguere tra un algoritmo O(n) (ovvero che
cresce proporzionamente a n) ed uno O(m^n) (ovvero che cresce
esponenzialmente rispetto a n) *prima* di scrivere codice, la scelta
tra due algoritmi con le stesse caratteristiche tendenziali e'
opportuno farla dopo aver misurato le prestazioni effettive.
Ciao,
Nicola

 proporzionale a n, quindi e' assolutamente preferibile.
Ovviamente lo stesso approccio si puo' seguire anche per
un'implementazione ricorsiva che restituira' gli ultimi due valori,
invece che solo l'ultimo; ad esempio:
#include <utility>
#include <iostream>
typedef std::pair<int,int> pair;
pair fib2(int n) {
  if ( n == 0 ) return pair(0,1);
  else {
    pair v = fib2(n-1);
    return pair(v.second,v.second+v.first);
  }
}
int fib(int n) {
  return fib2(n).second;
}
int main() {
  std::cout << fib(7) << '\n';
}
Ciao,
Nicola

 "infinita" (fino a che c'e' memoria a disposizione).
Ammetto di non aver notato il tipo. Ma in ogni caso
non ho la sfera di cristallo per conoscere le specifiche dei tipi
che ti definisci da solo. Nel messaggio non lo dicevi.
Comunque se ti occupi di calcoli con numeri in precisione arbitraria
ti consiglio di usare delle librerie tipo gmp. Con gmp nel mezzo secondo
di cui dicevi si puo' calcolare fib(5000) circa 35 mila volte...
ciao,
g.

 circa 35 mila volte...
CInfInt e' stata scritta parecchi anni fa mentre stavo imparando il
C++...
Ci sono affezionato, tutto qui. So che non e' uno strumento
professionale e ne conosco i limiti.
Ad ogni modo non mi occupo di calcoli in precisione arbitraria e.... se
dovessi farlo conosco le librerie da usare.
Inoltre il "meno di mezzo secondo" e' sparato a caso, ad essere sincero
non noto delay...
Ora ho fatto un timing piu' accurato e su un AMD XP2200+ ci mette 62ms
in media.
Questo risultato e' molto probabilmente molto piu' lento che con gmp, ma
come ti ho detto non mi interessava farlo in 1ms, ho abbastanza pazienza
da aspettare anche 62ms.
Il punto della dimostrazione era che con il classico metodo ricorsivo ci
vuole ben di piu' che 62ms anche usando gmp!!! Provare per credere, io
per fare fib(5000) con ricorsione classica non ho abbastanza pazienza...
forse tu se sei un immortale si!


 intelligenza.
il risultato non lo davi nel messaggio. Qui non si tratta di insultare
nessuno o dare del bugiardo a nessuno, cosa che di solito non faccio.
Una disattenzione puo' capitare a tutti, almeno a me capita spesso. La 
stragrande maggioranza delle  persone che bazzicano il gruppo ha scarsa 
esperienza. Quindi puo' succedere, almeno a me, di dire cose che magari
sono ovvie per la persona a cui rispondo, ma che magari possono 
interessare qualche altra persona. Non posso conoscere i profili
di tutti i partecipanti. Non prenderla come una cosa personale.
Chiuderei qui questa discussione.
Se puo' servire mi scuso per il mio tono e per tutto il resto.
ciao,
g.

 invece che solo l'ultimo; ad esempio:
gia', ma questo e' un approcio iterativo trasformato in ricorsivo... non e'
l'approcio ricorsivo classico fornito dalla definizione "matematica" dei
numeri di Fibonacci.
Ad ogni modo ci avevo pensato pure io ieri sera ed ero indeciso se
implementarlo o meno ;-)
E' stato buffo vedere che un altro ha avuto la mia stessa idea!
Carino davvero l'uso di pair che fai, io a questo non avevo davvero
pensato...
Dal momento che ho apprezzato la tua soluzione spero cha anche a te possa
interressare la mia... questo era quello a cui avevo pensato io:
<CODE>
int Rico_Fibo2(const int n, int iter, int prev1, int prev2)
{
      if(iter>n)
            return prev1;
      else
            return Rico_Fibo2(n,iter+1,prev1+prev2,prev1);
}
int Rico_Fibo(const int n)
{
      if(n<2)
            return n;
      return Rico_Fibo2(n,2,1,0);
}
int main()
{
      cout << Rico_Fibo(7) << endl;
      return 0;
}
</CODE>
Ovviamente non e' in stile C++ come la tua.... e poi e' pensata diversa
(ritorno un solo valore e ne passo piu' di uno... il contrario esatto di
quello che fai tu).
Proprio perche' sono diverse mi e' piaciuto molto vedere la tua e la ho pure
apprezzata parecchio!
Detto questo sono entrambi "castroni" fatti per divertirsi, la versione
iterativa e' preferibile. (questo ho dovuto dirlo altrimenti sarebbero
partite polemiche ;-)
Ciao,
Tommy

 Se puo' servire mi scuso per il mio tono e per tutto il resto.
Concordo. Le tue scuse non servono... 
Credo che sia stato chiarito tutto! ;-)
Alla prossima,


 pochino anche il mio... :-(
Il fatto che (anche se positivamente) qualcuno possa identificarmi
e giudicarmi in base ai mei post o anche semplicemente ricordare il
mio nome lo trovo un pensiero inquietante :-)
Io invece, sara' che nel 2004 faccio 40 anni (sigh!) ma a volte
devo guardare la patente per ricordarmi come mi chiamo io...
figuriamoci gli altri, senza offesa.
(sono patologico per quanto riguarda i nomi, lo so)
ciao,
g.

 pensato...
Se non sbaglio, e' il classico utilizzo della funzione coppia per tenere 
la "storia" di una funzione, cosi' come si insegna ai corsi di 
informatica teorica et similia per implementare fibonacci con formalismi 
abb deboli, tipo le funzioni primitive ricorsive - am I right?
-- 
/**
  * Mattia Belletti - Undergraduate student @ 
cs.unibo.it
  * ICQ: 33292311   - email: 
mbel...@cs.unibo.it
  * IRC: BluShine   - site(s): 
http://cs.unibo.it/~mbellett
  * Linux registered user 299762 @ Linux registered machine 213003
  */

 :-)
Da un certo punto di vista, approvo!
Gli algoritmi ricorsivi sono sempre affascinanti.
Vorrei riprendere il discorso e aggiungere...tornando alla vita (e alla
programmazione) reale, io uso una semplice regoletta pratica: tutte le volte
che è possibile evitare la ricorsione, senza diventare matti, è bene farlo!
E questo non perché sia sbagliato usare la ricorsione, ma forse perché, non
è proprio necessaria in quei casi... E' solo estetica (per quanto
affascinante)!
Ad esempio, il fattoriale per un informatico è un ciclo di moltiplicazioni,
per un matematico è fatt(N)=N*fatt(N-1)... Ovviamente il risultato è lo
stesso, però l'efficienza nel calcolo per un fattoriale qualsiasi, cambia
notevolmente.
Diverso è il discorso ad esempio in molti algoritmi dei giochi...

 Diverso č il discorso ad esempio in molti algoritmi dei giochi...
Cioe?

 ;-)
Questo ( 
http://www.acm.org/sigsoft/SEN/deutsch.html
 ) permette di
capire qualcosa in piu' :-)
Ciao,
Nicola

 Cioe?
Giusto per fare un esempio, un algoritmo minimax iterativo diventa
complicato... come esperimento l'ho fatto ma non ne valeva proprio la
pena...

 pena...
no, non ne vale davvero la pena...
In generale quando l'iterazione non fa altro che emulare la ricorsione non
conviene.
Nel caso del minimax dovresti crearti una struttura dato Stack ed usarla
come viene utilizzato lo stack nella ricorsione, in pratica fai quello che
la ricorsione fa con il risultato che ci metti 10 volte piu' tempo, rischi
ci siano bugs e magari e meno ottimizzato di quanto non faccia il
compilatore con la ricorsione.
E poi quando si scrive un "gioco" con minimax ci sono tante ottimizzazioni
specifiche del gioco (oltre a quelle non specifiche tipo alfa-beta,
transposition-tables etc..) su cui conviene investire tempo tipo aperture (e
chiusure di gioco), una buona evaluation function etc...
Tommy

>CInfInt ovvero un mio intero scritto da ma a precisione
"infinita" (fino a che c'e' memoria a disposizione).
potresti spiegarmi come si fa una cosa del genere (o quanto meno dove possa
trovare delucidazioni al riguardo)? ho letto delle gmp, ma è per imparare,
mica altro...