Last Updated on September 22, 2023 by Mayank Dham
Recursion in Java is a powerful programming technique that enables a function to call itself, allowing for elegant solutions to complex problems. Java, a versatile and widely-used programming language, embraces recursion as a fundamental concept. In this article, we delve into the world of recursion program in Java, exploring its principles, benefits, and pitfalls. From basic recursive functions to advanced recursive algorithms, we navigate the depths of this paradigm to empower you with the skills to leverage recursion in Java effectively in your programming endeavors.
What is Recursion?
Recursion is a divide-and-conquer problem-solving strategy. In the divide-and-conquer strategy, we divide the problem into smaller problems of the same category and solve the smaller problems to combine them and form the overall solution for a large problem. So, in recursion too, we divide our problem into smaller problems.
Recursion is a mathematical concept of solving a big problem using the solution of a small problem of the same kind. For instance, if we want to find the factorial of 5, and we know the factorial of a smaller problem, say the factorial of 4, then we can find the factorial of 5 by multiplying 5 with the factorial of 4 i.e. 5! = 5 x 4!.
So, you can see the larger problem (5!) and the smaller problem (4!) are of the same kind (i.e. finding the factorial).
Recursion in programming can be understood as a function calling itself. The basic syntax of a recursive function looks like this.
Please note that the number of times a method calls itself is not limited to 1 i.e. a method can call itself a number of times too. This will also be recursion. This call to the method inside the method itself is known as a recursive call.
So, now that we have some basic idea about recursion, let us write a recursion program in Java.
Recursion Program in Java – Print Decreasing Counting
Consider that we take a number input from the user (say the user enters 5). Now, we have to print the reverse counting or decreasing counting i.e. 5,4,3,2,1. We will perform this using recursion.
So, consider the following image shown below.
Printing the counting from 5 to 1 is a bigger problem and printing the counting from 4 to 1 is a smaller problem. We can solve the bigger problem from the smaller problem as shown.
So, we can see that we have defined a relationship between the big problem and the small problem. Now, let us understand what happens inside the call stack memory in Java.
Recursion Call Stack
Consider the image shown below.
So, instead of 5, we have generalized the function for the user input N and the recursive call also. The call stack is empty right now. Now, consider that the user enters the input N=5. So, a call will be made and it can be shown in the call stack as follows.
So, the function gets on the function call stack. The local variable N of the function gets assigned the value 5. Now, when the function is there on the call stack, it starts executing. So, the first line executes. Since it is a print statement to print the value of N, N=5 gets printed and is shown under the Output. Now, the second line executes. Since the second line is a recursive call to a function, we can say that this function as soon as hits the second line, makes a recursive call and thus this function pauses itself as a call is being made to the new function. Thus, the word pause is written after 2 in the image.
So, the recursive function call is made successfully as shown below.
So, the same happens with this recursive call also i.e. after printing the value of N, it hits a recursive call to N-1. So, some of the recursion calls are shown below.
Now, the call will be made to N-1=1-1=0. So, what do you think will happen? Yes, 0 will be printed and the call will be made to N=-1. Then, -1 will be printed and the call will be made to N=-2, and so on.
This will never stop. Since the call stack is a memory, it will get full at some time and we will get a StackOverflow exception when this memory will be full. Moreover, we didn’t even want to print -1, -2, and so on. We just wanted to print the values till 1. So, we have to stop as soon as N becomes 0. This is done as follows.
So, we have added a condition in the function that as soon as N becomes 0, we return. So, let us see what happens.
So, when N = 0, we hit the condition in the if block, and there is only one statement i.e. return. So, we return from there and we go to the function lower than that in the stack. This condition that stops the recursion call stack to give the StackOverflow exception is called the base condition or base case.
Now, when we are at N=1, we have completed all the statements in the method. So, all we have to do is terminate this method i.e. return.
So, the above image shows that we are returning from printDecreasing(1) and printDecreasing(0) has been wiped out of the stack.
Similarly, all the functions will be wiped out of the stack.
So, now that we have understood the recursion call stack, base case, and how recursion calls are made, let us write the recursion program in Java to print the counting in reverse order.
Recursion Program in Java – Print Decreasing Counting
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
// write your code here
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
printDecreasing(n);
}
public static void printDecreasing(int n){
if(n == 0) return; //base case
System.out.println(n);
printDecreasing(n-1); //recursive call
}
} Time Complexity of Print Decreasing recursion program in Java: The time complexity can be determined by the number of recursion calls made and the work done in each recursion call. Since we are just having a print statement and recursion call in each call, the time taken in each call is O(1). Since we are making N+1 calls in total (height of the recursion call stack), the total time complexity becomes O(1) * (N+1) i.e. O(N).
Space Complexity of Print Decreasing Recursion program in Java: Since we have not used any extra data structure, the auxiliary space is O(1). However, recursion space can be determined by the height of the recursion call stack. So, the recursion space is O(N).
Now that we have seen a simple Recursion program in Java without any return type, let us now see a program with an int return type.
Recursion Program in Java – Factorial of a Number
We know that the factorial of a number N can be calculated using the recurrence relation as:
Factorial(N) = N * Factorial(N-1)So, we will just use the above statement. However, what will be the base case? The base case in a recursive function is usually the smallest problem to which the solution is already known to us.
So, in the case of finding the factorial of a number, the smallest factorial that we can find is 0! and we know that 0! is 1. So, this will be the base case i.e. when N=0, return 1.
We request you draw the recursion call stack diagram on your own to get a better and clear understanding and for your own practice. Let us now see the recursion program in Java to find the factorial of a number.
Recursion Program in Java – Factorial of a Number
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
// write your code here
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
System.out.println(factorial(n));
}
public static int factorial(int n){
if(n == 0) return 1;
return n * factorial(n-1);
}
} Time Complexity of Factorial of a Number recursion program in Java:
The time complexity is O(N) because we are making N+1 recursion calls and the work done in each recursion call is O(1).
Space Complexity of Factorial of a Number recursion program in Java:
The auxiliary space is O(1) as we have not used any extra space. The recursion space is O(N) which can be seen from the height of the recursion call stack.
So, we have learned to recursion program in Java, one for printing the counting in reverse order and another to calculate the factorial. We hope that you have understood what recursion is and how you can write your own recursion program in Java. We hope to see you again soon at PrepBytes.
Conclusion
In the realm of programming, recursion stands as a versatile tool that unlocks innovative solutions to problems that might seem intricate at first glance. As you conclude this journey through recursion in Java, you are equipped with a powerful technique that can simplify complex tasks and streamline code. By understanding the core principles, identifying appropriate use cases, and exercising caution to prevent infinite recursion, you possess the skills to harness recursion’s potential and craft elegant and efficient solutions to a wide range of programming challenges.
FAQ Related to recursion program in Java
Here are some FAQs related to recursion program in Java.
Q1: What is recursion in programming?
Recursion is a programming technique where a function calls itself to solve a problem. It’s a way of breaking down complex problems into smaller, more manageable sub-problems.
Q2: What are the benefits of using recursion?
Recursion can lead to more elegant and concise code, especially when dealing with tasks that have a recursive structure. It can simplify complex problems and allow you to express solutions in a more natural way.
Q3: What is the base case in recursion?
The base case is a condition that defines when the recursion should stop. It’s the simplest form of the problem that can be solved directly without further recursion.
Q4: How does recursion work in Java?
In Java, a recursive function calls itself with modified arguments to solve smaller instances of the same problem. Each recursive call takes the problem closer to the base case.
Q5: Can recursion replace iterative loops?
Recursion and iteration are two different approaches to solving problems. While recursion can replace some iterative constructs, each has its strengths and weaknesses. The choice between them depends on the problem and coding style.