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).