我只是想知道当您需要返回值并比较它们以找到最佳解决方案(例如动态编程)时是否可以用显式堆栈替换递归?
所以类似(它没有做任何事情,只是一个例子):
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;
}
最佳答案
是的。这是可能的。
只需根据需要进行推送和弹出即可。递归只是创建一个“隐式堆栈”。您还可以展开 TCO 递归函数。
您可能会找到Stacks and Recursion Elimination (这是一门类(class))有用。它涵盖消除(左递归)以及模拟(堆栈)。
关于recursion - 用显式堆栈替换递归(带返回值),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4006450/