Recursion
Recursive functions, the Fibonacci series and The Golden Ratio
Leonardo of Pisa, better known as Leonardo Fibonacci was a wealthy Italian
merchant of the thirteenth century. He familiarised Europe with the fruits
of the Hindu-Moslem contribution to mathematics.
In an item of his book "Liber Abaci" he explained the simplest type of nonrecurrent
series, namely that formed by the expression Un = Un1 + Un2.
Simply stated, this series of numbers, which has come to be known as the Fibonacci series,
starts with 0 and has the property that each successive number is the sum of the two
previous e.g. 0, 1, 1, 2, 3, 5, 8, 13, 21...
The ratio of successive Fibonacci numbers converges on the constant value of 1.618...
This number is referred to as The Golden Ratio,
it repeatedly occurs in nature, describing a form of spiral.
It transpires that this series turns up in almost every facet of the part of
genetics concerned with how individuals of different genotypes change in successive
generations.
The Fibonacci series is used to demonstrate recursion in the following function.
Recursion is where a function calls itself until the base case is realised.
| Recursion |
The Fibonacci Series
|
|
long Fibonacci(long n)
{
if(n == 0 || n == 1) return n;
else return Fibonacci( n - 1 ) + Fibonacci( n - 2 )
}
|
Note: Despite the simple elegance of recursion, there are two good reasons
to generally prefer iterative solutions.
- The overhead of a function call is not as quick as iteration.
- The danger of stack overflow is substantial.
|
|
|
| Fibonacci Function object |
A fibonacci generating function object and driver for the STL.
|
|
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
class gen_fib
{
int last;
int prev;
public:
gen_fib() :last(0), prev(0) {};
int operator() ();
};
int
gen_fib::operator() ()
{
if( !last ) return last =1;
if( !prev ) return prev =1;
int rv = prev + last;
prev =last;
return last =rv;
};
typedef ostream_iterator<int> IntOsIt;
void main()
{
vector<int> v(10);
IntOsIt out(cout, " ");
generate( v.begin(), v.end(), gen_fib() );
copy( v.begin(), v.end(), out );
cout<< "\nPress any key to exit... ";
while( !cin.get() )
;
}
|
Note: The function object gen_fib generates successive
Fibonacci numbers with each successive call.
The function object is used with the algorithm generate
to initialise an STL vector object.
Note also the use of the ostream_iterator iterator used to
print the contents of the vector object.
|
|
|
|
|
