This is a post I’m resurrecting from my old blog because it deals with an interesting mathematical subject, Fibonacci numbers. Apparently, the acclaimed 13th century mathematician Leonardo Fibonacci applied the numerical sequence in solving a problem involving the growth of a hypothetical rabbit population.

The sequence is commonly defined as

*f(0)* = 0

*f(1)* = 1

*f*(*n*) = *f*(*n* − 1) + *f*(*n* − 2)

This is a mathematical recursive definition (aka recurrence) because we have defined f(n) in terms of f, specifically f(n-1) + f(n-2).

Here’s the start of the sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

For some reason computer science books like to teach recursion by using Fibonacci numerical sequences. However, you can also generate the sequence iteratively with a programming language.

So let’s see how we might use PHP to generate this mathematical sequence that apparently commonly occurs in nature.

<?php
/**
* Example using recursion: It works but very
* impractical to apply recursion b/c
* redundant calls cause web server to slow down
*
**/
function fibonacci($n)
{
if($n == 0)
return 0;
elseif ($n == 1)
return 1;
else
return fibonacci($n - 1) + fibonacci($n - 2);
}
for($i = 0, $max = 35; $i < $max; $i++) // zero-based indexing
{
echo fibonacci($i) . " ";
}
/**
* Better approach for a web server is to employ iteration instead
* getFibSequence()
* @param $num - sequence length
* faster than using recursion, no redundant calls
* by Sharon Lee Levy, ZCE
**/
<?php
function getFibSequence( $num ) {
$seq = array( 0, 1 ); // by definition sequence begins
if ( $num == 0 ) return 0;
if ( $num == 1 ) {
// return sequence unchanged
}
if ( $num >= 2 ) // now things get interesting
{
for ( $i = 0, $max = $num-2; $i < $max; $i++ ) { // first 2 nums of sequence already defined
$fib = $seq[$i] + $seq[$i+1];
$seq[] = $fib; // note the appropriate use of array[] technique
}
}
return implode(" ", $seq );
}
echo getFibSequence(35);

You can also use a closure to get the fibonacci sequence which is illustrated below.

<?php
$first = 0;
$second = 1;
$n = 10;
$inc=1;
$seq = array(0,1);
$f = function($a,$b) use( &$seq ) {
$final = $a + $b;
$a = $b;
$b = $final;
$seq[] = $final;
return (array("first"=>$a,"second"=>$b));
};
do{
$temp = $f($first,$second);
$first = $temp["first"];
$second = $temp["second"];
$inc++;
}
while ($inc < $n) ;
var_dump($seq);
?>

This work is licensed under a

.

### Like this:

Like Loading...

*Related*

## Leave a Reply