Замена рекурсии (с возвращаемыми значениями) с явным стеком

Question

Мне было просто интересно, можно ли заменить рекурсию явным стеком, когда вам нужны возвращаемые значения и сравнивают их, чтобы найти лучшее решение (например, динамическое программирование)?

Так что-то вроде (ничего не делает, просто пример):

int resursiveFunction (int state) { 

   if (known[state]) return cache[state];
   if (state == MAX_STATE) return 0;

   int max = 0;

   for (int i = 0 ; i < 5; i++) {
      int points = curPoints (state) + recursiveFunction (state+i);
      if (points > max) max = points; 
   }

   known[state] = true;
   cache[state] = max;
   return max; 

}

Answer 1

Да.Это возможно.

Просто нажмите и вытолкните как нужно.Рекурсия просто создает «неявный стек».Вы также можете отменить рекурсивные функции TCO.

Вы можете найти Стеки и удаление рекурсий (это для курса).Он охватывает исключение (леворекурсивное), а также эмуляцию (стек).