Преобразование рекурсивного решения в итеративный

Question

У меня есть экзамены на среднесрочную перспективу на следующей неделе, и я столкнулся с проблемой, которую я просто не могу взломать (я считаю, что рекурсия настолько запутанной!). Мне нужно преобразовать эту рекурсивную функцию в итеративную, я ценю любую помощь/подсказки и т. Д.!

рекурсивное решения:

long F(int n) { 
    if (n >= 0) { 
     if (n >= 3) { 
      //std::cout << "Current n is: " << n << std::endl; 
      long result = 0; 
      result = 3 * F(n - 1) + 2 * F(n - 2) + F(n - 3); 

      //std::cout << "Current result is : " << result << std::endl; 
      return result; 
     } 
     else { 
      return n; 
     } 
    } 
    else { 
     return -1; 
    } 
} 

Моей попытка итерационным решения:

long F2(int n) { 
    if (n >= 0) { 
     long outterResult = 0; 
     long innerResult = 0; 

     for (int o = n; o >= 3; o--) { 
      outterResult += innerResult; 
      int iteration = 1; 
      for (int i = 3; i > 0; i--) { 
       innerResult += i*(n-iteration); 
       iteration++; 
      } 
      //std::cout << "Current n is: " << n << std::endl; 
      //std::cout << "Current result: " << outterResult << std::endl; 
     } 
     return outterResult; 
    } 
    else { 
     return -1; 
    } 
} 

Ура!

Answer 1

В этом случае подход с динамическим программированием выполнит задание - начните снизу вверх при n == 0 и сохраните результаты последовательных значений n в массиве. Нечто подобное (это псевдокод):

for(int i = 0; i <=n ;++i) 
    if(i < 3) 
     arr[i]=i; 
    else 
     arr[i] = 3 * arr[i-1] + 2 * arr[i-2] + arr[i-3] 

return arr[n];