RECURSION
The process in which a function calls itself directly or indirectly is called Recursion and the corresponding function is called a Recursive function.
 |
| Recursion |
Recursion is used to solve problems involving iterations in reverse order. It solves a problem by reducing it to an instance of the same problem with smaller input. Recursion is an alternative to each iteration in making a function execute repeatedly.
PROPERTIES OF RECURSION:
A recursive function can go infinite like a loop, to avoid infinite running of the recursive function.
There are two properties that a recursive function must have:
1. Base Criteria: There must be at least one base criteria or condition such that when this condition is met the function stops calling itself recursively.
2. Progressive Call: The recursive calls should progress in such a way that each time a recursion call is made, it comes closer to the base case.
The classic example of recursive programming involves computing factorials. The factorial of a number is computed as that number times all of the numbers below it up to and including 1.
int fact(int n)
{
int x,y;if(n==0)
{
return 1;}else{x=n-1;y=fact(x);return(n*y);}
}
5!
=5*4!
=5*4*3!
=5*4*3*2!
=5*4*3*2*1!
=5*4*3*2*1*0!
=5*4*3*2*1
=5*4*3*2
=5*4*6
=5*24
=120
DIFFERENCE BETWEEN ITERATIVE AND RECURSIVE FUNCTION
| Iteration | Recursion |
|---|---|
| IterationIt is a process of executing statements repeatedly until some specific condition is specified. | RecursionRecursion is a technique of defining anything in terms of itself. |
| IterationIteration involves four clear cut steps, initialization, condition, execution, and updating. | RecursionThere must be a base condition inside the recursive function specifying the stopping condition. |
| IterationThe value of the control variable moves towards the value in the condition. | RecursionThe function state converges towards the base case. |
| IterationAny recursive problem can be solved iteratively. | RecursionNot all problems have a recursive solution. |
| IterationIteration code tends to be bigger in size. | RecursionRecursion decrease the size of code. |
| IterationAn iteration does not use the stack so it's faster than recursion. | RecursionIt is usually much slower because all function calls must be stored in a stack to allow the return back to the caller functions. |
| IterationIteration consumes less memory. | RecursionRecursion uses more memory than iteration. |
Types of Recursive Functions:
A recursive method is characterized based on:
Whether the method calls itself or not (direct or indirect recursion)
Whether there are pending operations at each recursive call (tail-recursive or not)
Direct Recursion:
If a function calls itself, it’s known as direct recursion. A function f1 is called direct recursive if it calls the same function say f1. E.g.
int fibo (int n)
{
if (n==1 || n==2)
return 1;
else
return (fibo(n-1)+fibo(n-2));
}Indirect Recursion:
When a function is mutually called by another function in a circular manner, the function is called an indirect recursion function. If the function f1 calls another function f2 and f2 calls f1 then it is indirect recursion (or mutual recursion). E.g.
int func1(int n)
{
if (n<=1)
return 1;
else
return func2(n);
}
int func2(int n)
{
return func1(n);
}Tail Recursion:
A recursive function is called the tail-recursive if the function makes a recursive calling itself, and that recursive call is the last statement executed by the function. After that, there is no function or statement left to call the recursive function.
void print(int n)
{
if(n==0)
return;
else
printf("Number is: %d",n);
return print(n-1);
}Non-Tail Recursion:
A function is called the non-tail or head recursive if a function makes a recursive call itself, the recursive call will be the first statement in the function. It means there should be no statement or operation called before the recursive calls.
void print(int n)
{
if(n>0)
{
print(n-1);
print("%d",n);
}
}Time Complexity:
We try to figure out the number of times a recursive call is being made. If n number of times a recursive call is made then the time complexity of the recursive function is Ο (2n) while the iterative function is O (n).
Space Complexity:
Space complexity is counted as what amount of extra space is required for a
module to execute. In iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used and space complexity is O (1). But in recursion, the system needs to store activation records each time a recursive call is made and space complexity is O (n).
Application of Recursion:
- The most important data structure ‘Tree’ doesn’t exist without recursion we can solve that in an iterative way also but that will be a very tough task.
- The mathematical problem can’t be solved in general, but that can only be solved using recursion up to a certain extent.
- Sorting algorithms (Quick sort, Merge sort, etc.) uses recursion.
- All the puzzle games (Chess, Candy crush, etc.) broadly uses recursion.
- It is the backbone of searching, which is the most important thing.
- This is the backbone of AI.