Ecriture du code récursif itérativement

Question

J'ai le code récursif suivant que je veux changer en code itératif. Je ne sais pas par où commencer car la fonction est très complexe avec des appels récursifs à deux endroits. Des implémentations itératives possibles à la fonction ci-dessous?

int ncip(int dim, double R){ 
    int n, r = (int)floor(R); 

    if (dim == 1) 
     return 1 + 2*r; 
    n = ncip(dim-1, R); // last coord 0 

    for (int i=1; i<=r; ++i){ 
     n += 2*ncip(dim-1, sqrt(R*R - i*i)); // last coord +- i 
    } 

    return n; 
} 

Answer 1

Une approche courante consiste à utiliser une pile pour les appels de fonction. Une implémentation simple serait la suivante et vous pouvez faire une certaine optimisation dessus

int ncip(int dim, double R){ 
    typedef pair<int, double> data; // ties parameters into one unit 

    stack<data> s; 
    s.push(make_pair(dim,R)); // push the first set of parameters 
    int n = 0; 

    while(false == s.empty()) { // do the loop until stack is depleted 
     auto item = s.top(); // get the top item and pop it after 
     s.pop(); 
     int r = static_cast<int>(floor(item.second)); 

     if (item.first == 1) { 
      n += 1 + 2*r; 
     } else { 
      s.push(make_pair(item.first-1,item.second)); 

      for (int i = 1; i <= r; ++i){ 
       // since you have a multiplier 2 we push the same parameters twice 
       s.push(make_pair(item.first-1, sqrt(item.second*item.second - i*i))); 
       s.push(make_pair(item.first-1, sqrt(item.second*item.second - i*i))); 
      } 
     } 
    } 
    return n; 
}