Запись Рекурсивный код итеративно

Question

У меня есть следующий рекурсивный код, который я хочу изменить на итеративный код. Я не уверен, с чего начать, поскольку функция очень сложна с рекурсивными вызовами в двух местах. Любые возможные итерационные реализации для функции ниже?

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

Один общий подход заключается в использовании стека для вызовов функций. Простая реализация будет выглядеть следующим образом, и вы можете сделать некоторые оптимизации на нем

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