nth Fibonacci number

Find nth Fibonacci number without using recursion – only iteration

Because every recursive method or function can be made iterative as well (read here:Recursion vs iteration, let’s examine an iterative solution to this problem also.

Clearly, even in the iterative solution, we can return a 0 if n is 0, and if n is either a 1 or a 2 we should return a 1 – just look at the sequence again above if you need to be reminded why. But, what about calculating the fibonacci sum using a loop? Well, in the recursive case we go backwards – starting from the nth number we sum the n-1 and n-2 numbers until we hit a base case. But, using iteration it looks like we would have to go forwards instead of backwards – so our approach would have to be to start from the very beginning of the sequence and then to keep summing numbers until we reach the nth number in the sequence. And once we reach the nth number, we will of course have our answer.

So, with that in mind how do we start our iteration? Well, we should only start adding numbers in the sequence if n is greater than or equal to 3 – because we are already returning values for n less than 3. And, we will clearly need two variables to represent the previous 2 numbers in the sequence. Since we are starting at n equal to 3, those 2 variables should both be initialized to 1 in order to represent the first and second numbers in the sequence.

In the loop itself all we have to do is add the previous 2 numbers, save the sum of those 2 numbers along with the previous number and keep repeating this process until we get the nth Fibonacci number. Here is what the iterative solution to finding the nth Fibonacci number looks like in PHP:

Find nth Fibonacci number in PHP

function fibonacci($n) {

//0, 1, 1, 2, 3, 5, 8, 13, 21

/*this is an error condition
   returning -1 is arbitrary - we could
   return anything we want for this
   error condition:
*/
if($n <0)
return -1;

if ($n == 0)
return 0;

if($n == 1 || $n == 2)
return 1;

$int1 = 1;
$int2 = 1;

$fib = 0;

//start from n==3
for($i=1; $i<=$n-2; $i++ )
{
$fib = $int1 + $int2;
//swap the values out:
$int2 = $int1;
$int1 = $fib;
}

return $fib;

}

?>

And now we have our answers that allow us to find the nth Fibonacci number both iteratively and recursively.

Posted in PHP | Tagged , , | Comments Off

Comments are closed.