将函数从递归转换为迭代

Question

我有这个函数,我写的是非常慢,因为PHP不能很好地处理递归.我试图将它转换为while循环,但我无法绕过如何做到这一点.

谁能给我一些提示？

    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;
        }
    }
}

Answer 1

我不打算转换你的代码,但你可以通过创建一个堆栈将一个recusive函数转换为迭代函数:

$stack= array();

而不是调用$this->findroute(),将您的参数推送到此堆栈:

$stack[] = array($i, $distanceSoFar + $this->distanceArray[$curLoc][$i], $expectedValue);

现在将函数中的所有内容基本上包围在一个while循环中,在启动它之后耗尽堆栈:

while ($stack) { 
    // Do stuff you already do in your function here