如何将这个递归问题转化为迭代？由于最大递归深度被击中，线简化算法无法运行
回答 3
Software Engineering用户
发布于 2014-08-07 09:38:42
我会用最通用的方式进行模拟，如下所示:这就是我认为低水平机器会做的事情。
func(Param x) {
Stack stack = new Stack();
Frame frame = new Frame(x);
push(frame);
while (!stack.empty()) {
frame = stack.pop();
if (baseCase) {
createResult(frame);
} else {
newFrame = doWork(frame);
stack.push(frame);
stack.push(newFrame);
}
}
return frame.getResult();
}您可以按以下方式定义框架：
class Frame {
FrameData state;
Data sharedData;
Param inputParam;
Result getResult() {
..compute result from 'state' and 'sharedData'
}
}现在，您可能想知道，即使有两个递归调用，为什么只有一个推到堆栈中。这是因为第一次递归调用被推到堆栈中，与第二次调用推到堆栈的帧相比，具有不同的state和sharedData的帧。
既然你说了，你只需要接近和暗示。我希望这已经足够了。细节是在方法doWork()中完成的。在这里，Frame's实例变量发生了更改。
我花了一段时间想出这个。希望这里没有什么问题。
Software Engineering用户
发布于 2014-08-07 08:53:12
将递归算法转换为迭代算法通常需要做与编译器或解释器自己在幕后所做的相同的事情，即在场景的前面。这可能意味着您必须自己编写一个调用堆栈，并跟踪递归调用中的变量值，以便它们驻留在用户定义的数据结构中，而不是在系统提供的调用堆栈上。它比使用适当的递归更费劲，而且通常也更不可读性，但它允许您绕过系统限制--而不是达到内置递归限制--您只在动态分配数据的大小上达到内建限制。
当然，以完全不同的方式迭代解决相同的问题也是可能的，有时甚至更好。但是，它与其说是转换递归，不如说是用完全不同的东西替换它。这取决于这个问题是否可能。
Software Engineering用户
发布于 2014-08-16 18:11:32
我会使用堆栈，但尽量保持简单。毕竟，你需要知道下一步该做什么，就是一对数字。
def line_simple(array, epsilon):
keep = [False for i in array]
keep[0], keep[-1] = True, True
stack = deque()
stack.append((0, len(array) -1))
while len(stack) != 0:
left, right = stack.pop();
worst_distance, worst_index = find_worst(array, left, right)
if worst_distance > epsilon:
keep[worst_index] = True
stack.append((left, worst_index))
stack.append((worst_index, right))
return keep您所要做的就是编写find_worst。注意，find_worst应该像我所展示的那样使用参数；您不应该做find_worst(array[left:right])，它生成数组的副本。如果右左=0或1，请确保find_worst返回0。
https://softwareengineering.stackexchange.com/questions/252591
复制相似问题
腾讯云开发者
