You Must Know Recursion Before the Next Interview
Ready for your next interview today #5
In this story, I am going to discuss recursion. Recursion is one of the main problem-solving concepts of computer science. Therefore, you must know how to solve this kind of problems in your Engineering life. Every technical interviewer nowadays prepared to ask one or many problem-solving questions to measure the ability of your skill with problem-solving. One of them may be a recursion problem mostly. We solve our problems using iteration. Here I will show you how to solve some popular problem using recursion.
A recursion, we can see as a procedure where the solution to a problem depends on solutions to smaller instances of the same problem. So we break the task into smaller subtasks. Let’s go to the discussion.
So in summary, I am going to discuss…
- Add the first N numbers.
- Difference between Recursion and Iteration
- Head VS Tail Recursion
- Stack With Recursion
- Problem 1: House Building Problem
- Problem 2: How to Calculate the Factorial of a Given Number
- Problem 3: Towers of Hanoi
- Problem 4: Euclidian Algorithm
Add the first N numbers
Here let us see a simple example to get an introduction to what is a recursive function and how basically behave. Usually, we use a simple for/while loop but we can solve it with the help of recursive method calls.
private static void sumOfNnumbers(int N) {
int result = 0;
for(int i=1;i<N;++i){
result = result + i;
}
System.out.println(result);
}
// Result
45But, using the recursive approach we can do this easily and in a more logical way.
private static int sumOfNnumbers(int N) { if(N == 1) return 1;
return N + sumOfNnumbers(N-1);
}
// Result
45
Here the base case is to avoid infinite loops, If we do not mention a base case, the algorithm will run infinite times.
// Base case
if(N == 1) return 1;Here the N + sumOfNnumbers(N-1) is the sub-problem.
Content
- Difference between Recursion and Iteration
- Head VS Tail Recursion
- Stack With Recursion
- Problem 1: House Building Problem
- Problem 2: How to Calculate the Factorial of a Given Number
- Problem 3: Towers of Hanoi
- Problem 4: Euclidian Algorithm
Difference between Recursion and Iteration
Recursion is at least twice slower because first, we unfold recursive calls (pushing them on a stack) until we reach the base case and then we traverse the stack and retrieve all recursive calls.
Head vs Tail Recursion
If the recursive call occurs at the end of the method, It’s called tail recursion. Tail recursion is the same as a loop. The method executes all the statements before jumping into the next recursive call. Here is an example.
private static void tail(int N) {
if(N == 1) return;
System.out.print(N);
tail(N-1);
}
// Result
5 4 3 2If the recursive call occurs at the beginning of the method, it is called a head recursion. The method complete and saves the state before jumping into the next recursive call.
private static void head(int N) {
if(N == 1) return;
head(N-1);
System.out.print(N);
}
// Result
2 3 4 5Stack With Recursion
We have to store the pending data within a stack during the process is running. The system uses the Stack abstract data type for this purpose. So. we have to track during recursion who called the given method and what arguments are to be handed over. We just need a single data structure; the operating system does everything for us. These important data are to be pushed to the stack and values are popped from the stack.
Example: We want to add the first N numbers. The following two images show you how it solves with the stack data type. So these method calls and values are stored on the stack.
Let us see how to solve some problems with recursion.
Problem 1: House Building Problem
The purpose of this example is to show you the difference between iteration and recursion for more clarification.
First I show you the solution in a recursive manner.
private static void buildLayer(int height) {
if ( height == 0) return; // Base case
buildLayer(height - 1);
System.out.println("Building the Layer "+height);
}
// Result
Building the Layer 1
Building the Layer 2
Building the Layer 3
Building the Layer 4
Building the Layer 5Then you can easily see the solution using in for loop.
private static void buildLayer(int height) {
for(int i=1;i<=height;++i) {
System.out.println("Building the Layer " + i);
}
}
// Result
Building the Layer 1
Building the Layer 2
Building the Layer 3
Building the Layer 4
Building the Layer 5Problem 2: How to Calculate the Factorial of a Given Number.
The factorial function (symbol: !) says to multiply all whole numbers from our chosen number down to 1.
Example: 4! is shorthand for 4 × 3 × 2 × 1
Here I calculate the factorial of any number using a recursive method. The example shows the factorial 5 is equal to 120.
private static int factorial(int n) {
if(n == 1) return 1; // Base case
return n * factorial(n-1);
}
// Result
120Problem 3: Towers of Hanoi
This is another common problem that asks in programming interviews. The importance is, Interviewer expects the solution in a recursive manner.
It consists of three rods and a number of disks of different sizes which can slide onto any rod. The target is to move all the disks to another tower without mixing the sequence of arrangement. The running time complexity of the program also should O(2^n) which is the exponential time complexity. And you should follow the rules below.
- Only one disk can be moved among the towers at any given time.
- Only the “top” disk can be removed.
- No large disk can sit over a small disk.
There will be always situations like 4, where we have to manage to shift n-1 plates to the auxiliary rod, then we just have to put the largest to the last rod. These situations we see as the subcases of the whole problem, where we want to call to the next method. When the first rod has only one disk, we consider it as the base case. This is the sample code and the solution.
public static void main(String[] args){
int n = 5;
towerOfHanoi(n,'A','C', 'B');
}
static void towerOfHanoi(int n, char from_rod, char to_rod, char helper_rod)
{
if (n == 1)
{
System.out.println("Take disk 1 from rod " + from_rod + " to rod " + to_rod);
return;
}
towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
System.out.println("Take disk " + n + " from rod " + from_rod + " to rod " + to_rod);
towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
}
// Result
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 4 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 3 from rod C to rod B
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 5 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 3 from rod B to rod A
Take disk 1 from rod C to rod B
Take disk 2 from rod C to rod A
Take disk 1 from rod B to rod A
Take disk 4 from rod B to rod C
Take disk 1 from rod A to rod C
Take disk 2 from rod A to rod B
Take disk 1 from rod C to rod B
Take disk 3 from rod A to rod C
Take disk 1 from rod B to rod A
Take disk 2 from rod B to rod C
Take disk 1 from rod A to rod CProblem 4: Euclidian Algorithm
This algorithm is for finding the greatest common device(GCD). It is an efficient way to find the GCD of two numbers, the largest number that divides both of them without leaving a remainder. For example, GCD of 20 and 28 is 4 and GCD of 98 and 56 is 14. This is the recursive function for find the GCD.
public static void main(String[] args){
int n = 5;
System.out.println(gcdRecursive(98, 56));
}
static int gcdRecursive(int num1, int num2) {
if(num2 == 0) return num1;
return gcdRecursive(num2, num1 % num2);
}
// Result
14We use the Modulo operator to find the GCD and the process is running until finding it. That’s how the Euclidian algorithm is working.
Conclusion
This story gives you a piece of deep knowledge about recursion and how to solve interview questions you will face in your next interview. Hopefully, you have enjoyed it. Please feel free to ask any question you will face in the response section below. Also, ask any other related questions you have.
Happy Coding !!!!
Found this post useful? Kindly tap the 👏 button below! :)
