Iterativ rekursiven Code schreiben

Question

Ich habe den folgenden rekursiven Code, den ich in iterativen Code ändern möchte. Ich bin mir unsicher, wo ich anfangen soll, da die Funktion bei rekursiven Aufrufen an zwei Stellen sehr komplex ist. Irgendwelche möglichen iterativen Implementierungen für die folgende Funktion?

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

Ein gängiger Ansatz besteht darin, einen Stapel für die Funktionsaufrufe zu verwenden. Eine einfache Implementierung wäre wie folgt und Sie können einige Optimierung auf sie

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; 
}