A recursive algorithm simplifies a problem by breaking it down into sub-problems of the same type. The output of one recursion becomes the input for another recursion.
Table of Contents
More about Recursive Algorithm
Recursive algorithms get the result for the current input by executing simple operations on the reciprocal value for the simpler or smaller input. They do this by using smaller input values to call themselves.
When it comes to develop a recursive algorithm, we need to break the provided problem statement into two parts. The base case is the primary, and the recursive step is the second.
- Base Case: The simplest case of a problem is considered as the base case, which consists of a state and condition that ends the recursive function. When a certain condition is met, this base case assesses the result.
- Recursive Step: It computes the output by reaching the same function repeatedly but with smaller or more complex inputs.
For example, let’s consider that we have one simplified version of a problem:
Now we will break it down into two parts, as discussed above. You can see in the given picture the two parts or two steps representation:
Types of Recursion
The four varieties of recursive algorithms are:
- Direct Recursion
If a function continually calls itself in its same function block, then it is commonly known as direct recursion.
| int fun()
{ … … int fun(); } |
In this programme, there is a method called fun that calls itself in its function definition. We can therefore refer to it as straight recursive.
- Indirect Recursion
Indirect recursion occurs when a function invokes another function. The primary function is then called once again from this function.
| int num()
{ … … int sum(); } int sum() { … … int num(); } |
- Tailed Recursion
If a recursive function conducts recursive calling on its own and that recursive call is the function’s final statement, the function is said to be tail-recursive. After that, there is no longer a way or phrase to call the recursive function.
| int fun(int x)
{ printf(“%d”,x); fun(x-1); //Recursive call is last executed statement } |
- Non-Tailed Recursion
If the recursion call isn’t the last thing the function executes, it’s called non-tail recursive. There is still stuff to evaluate after returning.
| int fun(int x)
{ fun(x-1); printf(“%d”,x); //Recursive call is not the final implemented statement } |
Practice Problems
Q1. The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst-case time complexity of this function is O(nα), then the least possible value (accurate up to two decimal positions) of α is _________.
OPTIONS
1) 2.3219280
2) 2.3219282
3) 2.3219281
4) 2.3219283
Q2. Consider the following C function.
int fun (int n) {
int i, j;
for (i = 1; i <= n; i++) {
for (j = 1; j < n; j += i) {
printf(“%d %d”,i,j);
}
}
}
Time complexity of fun in terms of θ notation is _________.
OPTIONS
1) θ(n1/2n)
2 (θ(n log n)
3) θ(n2 )
4) θ(n2 logn)
Q3. Consider a list of recursive algorithms and a list of recurrence relations, as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.
Recursive Algorithm: P. Binary search Q. Merge suit R. Quicksort S. Tower of Hanoi
Recurrence Relation:
I. T(n) = T(n-k) + T(k) + cn
II. T(n) = 2T(n-k) +1
III. T(n) = 2T(n/2) + cn
IV. T(n) = T(n/2) + 1
Which of the following is the correct match between the algorithms and their recurrence relations?
1) P-II, Q-III, R-IV, S-I
2) P-III, Q-II, R-IV, S-I
3) P-IV, Q-III, R-I, S-II
4) P-IV, Q-II, R-I, S-III
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
