Generate Fibonacci Series

/*Pseudo code to generate Fibonacci Series using different types of Recursion Techniques */

Using Binary Recursion: Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it's using in data structure like operations for tree as traversal, finding height, merging, etc... Let see how Fibonacci series is generated!

Run Time Version Code:

int FibNum(int n)
{
// Base conditions
if (n < 1)
return -1;
if (1 == n || 2 == n)
return 1;

// Recursive call by Binary Method
return FibNum(n - 1) + FibNum(n - 2);


Compile Time Version Code

// Base Conditions
template<>
struct FibNum<2>
{
enum { val = 1 };
};
template <>
struct FibNum<1>
{
enum { val = 1 };
};

// Recursive call by Binary Method
template
struct FibNum
{
enum { val= FibNum::val + FibNum::val };
};

Tail Recursion: In this method, recursive function is called at the last. So it's more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.

Run Time Version Code:

int FibNum(int n, int x, int y)
{
if (1 == n) // Base Condition
{
return y;
}
else // Recursive call by Tail method
{
return FibNum(n-1, y, x+y);
}
}

Compile Time Version Code

template
struct FibNum
{
// Recursive call By tail method
enum
{
val = FibNum::val
};
};

// Base Condition or Termination
template
struct FibNum<1, x, y>
{
enum { val= FibNum::val + FibNum::val };
};