recursion confusion

Anon

Hello!

The two code exampels below makes me confused.

function countxs($x) {
if ($x<3) {
$x++;
echo($x.", ");
countxs($x);
}
echo(" send: ".$x);
return $x;
}

$a = countxs(0);

echo(" ==> recived: ".$a." ");

This code will produce an output like this:

1, 2, 3,
send: 3
send: 3
send: 2
send: 1 ==> recived: 1

I would have excpected this:
send: 3 ==> recived: 3

If I use the foolowing code instead I get even more confused.

function countxs($x) {
if ($x<3) {
$x++;
echo($x.", ");
countxs($x);
}
else {
echo(" send: ".$x);
return $x;
}
}

$a = countxs(0);

echo(" ==> recived: ".$a." ");

It will produce an output like this:

1, 2, 3,
send: 3 ==> recived:

So, how could I get a (recursive) function that behaves as I excpect?

Thanks
/Markus

dstockto

Write it to behave how you expect... I guess the question is, how do you want it to behave?

Think of recursion as using a stack to stack up calls... For example a recursive algorithm for determining a factorial would work something like this:

4! = 4 3!
3! = 3 2!
2! = 2 * 1!
1! = 1

Every time there is a ! for factorial there would be a function call. Once the funcion calls reach the exit condition (we know that 1! = 1) then each subsequent function call result can be passed back up the stack. So if we substitute 1! with 1, we can solve 2! since we can solve 2 1 = 2. If we now know 2! we can solve 3! since we know 3! = 3 2! = 3 * 2... Continue this way until the original function call (4!) is solved.

A thing to watch out for is recursive functions that do not have an exit condition.

For example, this would be a Bad Thing (TM) to do.

function bignumber($num)
{
return $num+bignumber($num);
}

That script is pretty much guaranteed to run PHP until it halts the script due to lack of memory or a timeout.

Dave

arabela

Hi!
You don't have to use a recursive function to do this. Try replacing the if statement for a while, like this:

while($x<3) {
$x++;
echo($x.", ");
countxs($x);
}
echo(" send: ".$x);
return $x;

Recursive functions are usually only used for solving mathematical problems (like the factorial) and can be a bit confusing sometimes.

Regards
Arabela

Anon

Ok, thanks for your comments. Actually the problem I had (not explicit the one I described before, but very similar) could be solved with a while-statement. Anyway, I think I understands how to deal with recursive functions in PHP now. I have some, (quite minor though), experience from LISP. LISP allows you to talk about a recursive function as recursive (the factorial example) or iterative (my sum example). The iterative type is completed when it stops for the exit condition, in my example that would be when $x=4, and do not need to return any value back to the 'calling environement'. Well, now I realize that's just what a return statement really do.

However, once aganin, thank you really much for your help! This is how you learn things 🙂

/Markus