- Recursion is one of the most powerful tools in a programming language, but one of the most threatening topics-as most of the beginners and not surprising to even experienced students feel.
- When function
**recursion**in C. The function which calls the same function, is known as**recursive function**. - Recursion is defined as defining anything in terms of itself. Recursion is used to solve problems involving iterations, in reverse order.

There are two types of Recursion

- Direct recursion
- Indirect recursion

When in the body of a method there is a call to the same method, we say that the method is **directly recursive**.

There are three types of Direct Recursion

- Linear Recursion
- Binary Recursion
- Multiple Recursion

- Linear recursion begins by testing for a set of base cases there should be at least one.

In Linear recursion we follow as under :

- Perform a single recursive call. This recursive step may involve a test that decides which of several possible recursive calls to make, but it should ultimately choose to make just one of these calls each time we perform this step.
- Define each possible recursion call, so that it makes progress towards a base case.

- Binary recursion occurs whenever there are two recursive calls for each non base case.

- In multiple recursion we make not just one or two but many recursive calls.

//C program for GCD using recursion #include int Find_GCD(int, int); void main() { int n1, n2, gcd; scanf(“%d %d”,&n1, &n2); gcd = Find_GCD(n1, &n2); printf(“GCD of %d and %d is %d”, n1, n2, gcd); } int Find_GCD(int m, int n) { int gcdVal; if(n>m) { gcdVal = Find_GCD(n,m); } else if(n==0) { gcdVal = m; } else { gcdVal = Find_GCD(n, m%n); } return(gcdVal); }

- It consumes more storage space the recursive calls along with automatic variables are stored on the stack.
- The computer may run out of memory if the recursive calls are not checked.
- It is not more efficient in terms of speed and execution time.
- According to some computer professionals, recursion does not offer any concrete advantage over non-recursive procedures/functions.
- Recursive solution is always logical and it is very difficult to trace.(debug and understand).
- In recursive we must have an if statement somewhere to force the function to return without the recursive call being executed, otherwise the function will never return.
- Recursion takes a lot of stack space, usually not considerable when the program is small and running on a PC.
- Recursion uses more processor time.
- Recursion is not advocated when the problem can be through iteration.
- Recursion may be treated as a software tool to be applied carefully and selectively.

Iteration |
Recursion |

In iteration,a problem is converted into a train of steps that are finished one at a time, one after another | Recursion is like piling all of those steps on top of each other and then quashing the mall into the solution. |

With iteration,each step clearly leads on to the next, like stepping stones across a river | In recursion, each step replicates itself at a smaller scale, so that all of them combined together eventually solve the problem. |

Any iterative problem is solved recursively | Not all recursive problem can solved by iteration |

It does not use Stack | It uses Stack |