recursion - 用显式堆栈替换递归(带返回值)

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'able 递归函数。

您可能会发现 Stacks and Recursion Elimination (这是一个类(class))有用。它涵盖了消除(左递归)以及仿真(堆栈)。