PDA

View Full Version : PHP Recursive Fibonacci Sequence



Ahlahn
05-29-2011, 04:10 PM
Hey guys,

I'm trying to write a recursive code that prints EACH value in the sequence leading up to the specified place. For example, if I enter 3, I will get

0 1 1

Here's what I have so far. It prints the nth number in the sequence- I don't know where to go from there.



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

}
$fib = fibRec(29);
echo $fib;

Fou-Lu
05-29-2011, 06:05 PM
Yeah, yours does appear to be short by one step. That will be because of this:


if($n==1){
return 0;
}

Fibonacci(1) should be 1, not 0. Fibonacci of 0 is 0 though.
I can see how you got here though, its a question of if your $n represents the number FROM 0 or INCLUDING 0.
Changing it to this:


if($n==0){
return 0;
}
else if($n<=2){
return 1;
}

With your standard $sum for the else, does provide me with the numbers as expected. I compared it against one I just wrote:


function fibonacci($n)
{
$iResult = 1;
if ($n == 0)
{
$iResult = 0;
}
else if ($n >= 2)
{
$iResult = fibonacci($n - 1) + fibonacci($n - 2);
}
else if ($n < 0)
{
$iResult = pow(-1, $n + 1) * fibonacci(abs($n));
}

return $iResult;
}

And got the same result for both with the above modification (except for the negatives since the algorithm you are using doesn't include the negafibonacci series).