Convert function from recursion to iteration

Question

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

Have you tried adding some sort of debug/print statements into the body of the for loop, showing when the recursion happens and how much. From inspection the code looks a bit odd to me. I'd check this before converting to use iteration. — DaveC, Dec 30 '09 at 22:54

score 8 · Accepted Answer · edited Oct 10 '12 at 02:26

8

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();

And instead of invoking $this->findroute(), push your parameters onto this stack:

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

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

edited Oct 10 '12 at 02:26

hakre

193,403
52
435
836

answered Dec 30 '09 at 22:42

Kristopher Ives

5,838
7
42
67

This has given me a good start but I'm having trouble figuring out what to do with the backtracking step. I need to set $this->locationsVisited[$curLoc] = true then iterate with it true and then turn it off again. – Eric Conner Dec 30 '09 at 23:23

score 2 · Answer 2 · answered Dec 30 '09 at 22:41

2

You can convert a recursive function into an iterative function by using a stack to store the current state. Look into array_push() and array_pop().

answered Dec 30 '09 at 22:41

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

score 0 · Answer 3 · answered Dec 30 '09 at 22:56

At a glance I don't think recursion is your problem, yes it's slow in PHP, but It looks like your going over values more than you need to, putting the values in a stack, or several stacks and handling them, may be nice.

custom sort functions have always helped me with problems of this sort.

function sort_by_visited($x,$y)
{
   return ($this->locationsVisited[$x] > $this->locationsVisited[$y]) ? -1 : 1;
}

uasort($locationsVisited,'sort_by_visited');

This will prioritize all not visited locations at the top of the stack.

score 0 · Answer 4 · answered Dec 30 '09 at 23:40

0

This looks like your trying to find the optimal route for traversal of a series of nodes in a graph.

I'm guessing that you've not studied Computer Science as the "Travelling Salesman" problem is an archetype of Artificial Intelligence. Of course, as such, it has its own Wikipedia page:

http://en.wikipedia.org/wiki/Travelling_salesman_problem

Sorry - but just swapping from a recursive to an iterative function isn't going to make it go any faster ("php does not handle recursion well." - can you provide reference for this assertion). If you need a faster solution then you'll need to look at non-exhaustive/fuzzy methods.

C.

answered Dec 30 '09 at 23:40

symcbean

47,736
6
59
94

"[7 Aug 1999 12:25pm UTC] zeev at cvs dot php dot net PHP 4.0 (Zend) uses the stack for intensive data, rather than using the heap. That means that its tolerance recursive functions is significantly lower than that of other languages. It's relatively easy to tell Zend not to use the stack for this data, and use the heap instead - which would greatly increase the number of recursive functions possible - in the price of reduced speed. If you're interested in such a setting, let me know, we may add a compile-time switch." I should probably just switch to C or something.. – Eric Conner Dec 30 '09 at 23:59
It says "tolerance" nothing about performance or reliablitiy - I think you'll find that the implication of this statement is the recursion is therefore limited by the stack size (which by default is much smaller than the heap in most setups. Switching your development to C isn't going to reduce the order of the algorithm - it'll still be N! C. – symcbean Jan 02 '10 at 23:26

Convert function from recursion to iteration

4 Answers4

Linked