将函数从递归转换为迭代 [英] Convert function from recursion to iteration
问题描述
我有这个函数我写的非常慢,因为php不能很好地处理递归。我正在尝试将其转换为while循环,但我无法绕过如何做到这一点。
I have this function that I wrote that is abysmally slow since php does not handle recursion well. I am trying to convert it to a while loop, but am having trouble wrapping my head around how to do it.
任何人都可以给我一些提示吗?
Can anyone give me some tips?
public function findRoute($curLoc, $distanceSoFar, $expectedValue) {
$this->locationsVisited[$curLoc] = true;
$expectedValue += $this->locationsArray[$curLoc]*$distanceSoFar;
$at_end = true;
for($i = 1; $i < $this->numLocations; $i++) {
if($this->locationsVisited[$i] == false) {
$at_end = false;
if($expectedValue < $this->bestEV)
$this->findRoute($i, $distanceSoFar + $this->distanceArray[$curLoc][$i], $expectedValue);
}
}
$this->locationsVisited[$curLoc] = false;
if($at_end) {
if($expectedValue < $this->bestEV) {
$this->bestEV = $expectedValue;
}
}
}
推荐答案
我不打算转换你的代码,但你可以通过创建一个堆栈将一个recusive函数转换成一个迭代函数:
I'm not going to convert your code, but you can convert a recusive function into an iterative one by creating a stack:
$stack= array();
而不是调用 $ this-> findroute()
,将你的参数推送到这个堆栈:
And instead of invoking $this->findroute()
, push your parameters onto this stack:
$stack[] = array($i, $distanceSoFar + $this->distanceArray[$curLoc][$i], $expectedValue);
现在将函数中的所有内容基本上包围在一个while循环中,在启动它之后耗尽堆栈:
Now surround basically everything in your function into a while loop draining the stack after having primed it:
while ($stack) {
// Do stuff you already do in your function here
这篇关于将函数从递归转换为迭代的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!