Recursion in data structures
- 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 is called within the same function, it is known as 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.
Types of Recursion
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
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)
gcdVal = Find_GCD(n,m);
gcdVal = m;
gcdVal = Find_GCD(n, m%n);
Disadvantages of Recursion
- 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.
Difference between recursion and iteration
|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