### Use of Memoization in Recursion

Memoization can be used to reduce function calls or computations. In the following example of Fibonacci series generation through C++, I will use normal recursion and then will change the same for memoization( http://en.wikipedia.org/wiki/Memoization ) to show the reduction of the function call. This is a simple demo implementation.
```static int counter = 0;
int normalfibrecursion(int n)
{
if( n < 1)
{
return 0;
}

if(n == 1)
{
return 1;
}

if(n < 3)
{
return 1;
}
else
{
cout << "Call normalfibrecursion(" << n-2 << ") and normalfibrecursion(" << n-1 << ")\n";
counter++;
return normalfibrecursion(n-2) + normalfibrecursion(n-1);
}
}
```
In the above-mentioned simple prototype implementation for the Fibonacci series of n=10, the total function call comes to (54*2) times. This is usually very high and it will grow exponentially as n increases. Below mentioned picture demonstrates the fact: USE OF MEMOIZATION: - The following example shows the use of memoization to optimize function calls.
```static int counter = 0;
int fib(int n, int *memoid)
{
if(memoid[n - 1] != -1)
{
return memoid[n - 1];
}

cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n";
memoid[n - 1] = fib(n-2, memoid) + fib(n-1, memoid);
counter++;
return memoid[n - 1];
}

int  memoidfib(int n, int *memoid)
{
for(int i = 0; i < n; i++)
{
memoid[i] = -1;
}
memoid=0;
memoid=1;

return fib(n,memoid);
}
```
If we call "memoidfib" function from our client code, definitely there will be a much-reduced function call and in this case, it is reduced to (8*2) function calls. Please follow the picture below: 