# Recursion

When a function calls itself, it is called recursion. Recursion can be direct or indirect. Recursion is very useful in solving certain problems that are difficult to solve using iterative methods. Tower of Hanoi is a very famous problem that is solved using recursion.

## Base Condition

While solving problems with recursion, the original problem is broken up into smaller problem until a smallest unit of problem hits which is directly solvable. This smallest unit is called base condition. The solution to base case is provided and is used to get the solution of the original problem.
Let’s see an exmple

``````int factorial(int n)
{
if (n == 1) // base case
return 1;
else
return n*factorial(n-1);
}
``````

In the above example, base case for `(n == 1)` is defined and larger value of number can be solved by converting to smaller one till base case is reached. The above program returns the factorial of the given number.

Base condition is very important and should be defined carefully. If not defined properly, recursion may never stop and overflow can occur.

## Direct/Indirect Recursion

Simply put, when a function continuously calls itself it is called direct recursion and when a function calls some other function continuously it is called indirect recursion.
Let’s see some examples

``````// An example of direct recursion
void foo()
{
//something
foo();
// Some code...
}
// An example of indirect recursion
void foo()
{
// Some code...
bar();
// Some code..
}
void bar()
{
// Some code...
foo();
// Some code...
}
``````

## Memory allocation for recursion

Whenever any function is called, memory for that function call is allocated on stack memory. The memory for called function is allocated on top of stack and copies of local variable are created for that function.
When the base case is reached and the execution of that particular function is over, the control is passed to the calling function and memory for the called function is popped off the stack i.e. the memory is deallocated.

### Program for Recursion

``````#include<bits/stdc++.h>
using namespace std;

void Fun(int t)
{
if (t < 1)
return;
else
{
cout << t << " ";
Fun(t-1);
cout << t << " ";
return;
}
}

int main()
{
int t = 3;
Fun(t);
}
``````

## Output

`3 2 1 1 2 3`
When `Fun(3)` is called from `main()`, memory is allocated to `Fun(3)` and a local variable test is initialized to 3 and statement 1 to 4 are pushed on the stack. It first prints 3. In statement 2, `Fun(2)` is called and memory is allocated to `Fun(2)` and a local variable test is initialized to 2 and statement 1 to 4 are pushed in the stack. Similarly, `Fun(2)` calls `Fun(1)` and `Fun(1)` calls `Fun(0)`. `Fun(0)` goes to if statement and it return to `Fun(1)`. Remaining statements of `Fun(1)` are executed and it returns to `Fun(2)` and so on. In the output, value from 3 to 1 are printed and then 1 to 3 are printed.