Rabbits and Numbers

2 04 2010

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 Creative Commons License
.

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: