The Fibonacci series (sequence, numbers) is an infinite sequence of integers, in which the first number is 0, the second 1 and every next number is defined as a sum of two preceding numbers. Hence the sequence starts with numbers
The series was discovered by Italian mathematician of the 12th century Leonardo Pissano (so called Fibonacci) as a model for growth of a rabbit population.
- At the beginning one pair of rabbits is born.
- Only rabbits older than one month can reproduce.
- Every productive pair of rabbits gives birth to one new pair of rabbits every month.
- The rabbits never die, when they start to mate, they never cease to.
Fibonacci series in algorithmics
From the point of view of algorithmics is the Fibonacci series very interesting problem, because it shows how inefficient algorithm may be created by simply rewriting the rules into the code. In this case the inefficient implementation is recursion based.
/**
* Fibonacci sequence using recursion
* @param index of the number (starting at 0)
* @return nth Fibonacci number
*/
public static int fibonacciRec(int index) {
if(index == 0) return 0;
else if(index == 1) return 1;
else return fibonacciRec(index - 1) + fibonacciRec(index - 2);
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
int fiborec(int to)
{
if (to == 0)
{
return 0;
}
else if (to == 1)
{
return 1;
}
else
{
return fiborec(to - 2) + fiborec(to - 1);
}
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
public static int FibonacciRec(int to)
{
if (to == 0)
{
return 0;
}
else if (to == 1)
{
return 1;
}
else
{
return FibonacciRec(to - 1) + FibonacciRec(to - 2);
}
}
/**
* Fibonacci sequence
* @param $to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
function fibonacci_rec($to) {
if ($to == 0) {
return 0;
}
else if ($to == 1) {
return 1;
}
else{
return fibonacci_rec($to - 1) + fibonacci_rec($to - 2);
}
}
Why is the recursive implementation inefficient?
The recursive implementation is by definition correct, but if we consider calculating the fifth Fibonacci number, than we have to calculate twice,
three times and trivial values will be calculated 8 times. With increasing value of the parameter the inffeciency only grows.
Iterative implementation of Fibonacci series
The solution is simple – transforming the problem into its iterative form, which can be done in this case by using a very simple form of dynamic programming (dynamic programming is based on remembering and reusing of already computed values). This can be done by introducing two helper variables that will be used to store the previous two Fibonacci numbers.
/**
* Fibonacci sequence using dynamic programming
* @param order of a number (counting from 0)
* @return Fibonacci number at the given position
*/
public static int fibonacci(int index) {
if(index == 0) return 0;
if(index == 1) return 1;
int prePre = 0;
int pre = 1;
int result = 0;
for(int i = 1; i < index; i++) { //calculate starting the index 2
result = prePre + pre; //result is sum of two preceding numbers
prePre = pre;
pre = result;
}
return result;
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
static int Fib(int to)
{
if (to == 0)
{
return 0;
}
if (to == 1)
{
return 1;
}
int last_last = 0, last = 1, result = 0, i;
for (i = 1; i < to; i++)
{
result = last_last + last;
last_last = last;
last = result;
}
return result;
}
/**
* Fibonacci sequence
* @param to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
static int Fibonacci(int to)
{
if (to == 0)
{
return 0;
}
if (to == 1)
{
return 1;
}
int last_last = 0;
int last = 1;
int result = 0;
for (int i = 1; i < to; i++)
{
result = last_last + last;
last_last = last;
last = result;
}
return result;
}
/**
* Fibonacci sequence
* @param $to order of a number (counting from 0)
* @return Fibonacci number at the given position
* @autor Thomas (www.adamjak.net)
*/
function fibonacciho_postupnost($to) {
if ($to == 0) {
return 0;
}
if ($to == 1) {
return 1;
}
$last_last = 0;
$last = 1;
$result = 0;
for($i = 1; $i < $to; $i++){
$result = $last_last + $last;
$last_last = $last;
$last = $result;
}
return $result;
}