Use of recursion in PHP

PHP
1

I was going through some basic mathematical problems and for fun I decided to use PHP (Normally I choose Python over PHP for this), to help me solve them. However, when I used recursion to solve a simple problem, I noticed that PHP would not handle it so well.

For example:

If I was to find the 10th number in the Fibonacci sequence, recursion is my best option and can be solved:


function fibo($n) {
    if ($n == 1)
        return 1;
    if ($n == 0 )
        return 0;
    return fibo($n-1) + fibo($n-2);
   }

But a simple function like that seems to exhaust my memory limit.

My question: Is PHP not built to handle recursive functions? Or should I just increase my memory size?

2

The problem with using recursion for this example is that it has to be recalculated from the beginning every single time you want a new number. Plus, you need to decide when you’re done, or else it will go on for ever (which was one of the problems with your function).

It’s much more efficient to story it in an array and access the array values.


function fibo($want, $a = array()) {
    // Set first levels if not set.
    if(!isset($a[0]) || $a[0] != 0) $a[0] = 0;
    if(!isset($a[1]) || $a[1] != 1) $a[1] = 1;
    
    // count levels
    $t = count($a);

    // Add last two numbers - the Fibonacci ratio
    $a[] = $a[$t-1] + $a[$t-2];

    // See if we've reached the level we want
    if($want >= count($a)) return fibo($want, $a);
    return $a;
   }

$f = fibo(10);
print_r($f);

You could also modify it to stop once you’ve reached a specific number, as opposed to a specific level.

If you want to do it without an array (which I don’t suggest), you can, but you just have to pass the last two generated numbers, since that’s how to actually get the next in the sequence.

An array is probably more resource-efficient.

3

Ah thats neat, it generates the sequence. Here is my little take on it =)


$a = 0;
$b = 1;
$limit = 10;

for ($i = 0; $i < $limit; $i++) {
    print $a . "<br>";
    list($a, $b) = array($b, $a + $b);
}

I originally did this in Python (much cleaner), then just ported it to PHP.


def fib(n):
	a = 0
	b = 1
	for i in range(n):
		print a
		a, b = b, a + b
4

Much cleaner, nice work. :cool:

Here’s an old PHP documentation note that maybe of interest too.
[URL=“http://www.php.net/manual/en/class.iterator.php#93580”]
http://www.php.net/manual/en/class.iterator.php#93580

5

Yeah my example is a terrible way to do it =p but I would have thought it would get it done rather quickly for small numbers. As I assumed the ==0 and ==1 would catch the base cases.

OK yeah I understand the problems imposed by my crappy function. Thanks for pointing that out =) The thought of using arrays had not even occurred to me for this problem lol.

6

I managed to solve it w/o recursion. Works much better =)


function fibo1($n){
    $sqrtOf5 = sqrt(5);
    $power = pow((($sqrtOf5 + 1) / 2),$n);

    return round($power / $sqrtOf5);

}

Thanks for the help though =)