In this article, we will write a recursion program in Java. We will understand the meaning of recursion, how the recursion call stack works, and the base condition in recursion, and write a recursion program in Java with void return type and a recursion program in Java with some other return type. So, let’s get started.
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.
Other Java Programs
Java Program to Add Two Numbers
Java Program to Check Prime Number
Java Program to Check Whether a Number is a Palindrome or Not
Java Program to Find the Factorial of a Number
Java Program to Reverse a Number
Java Program to search an element in a Linked List
Program to convert ArrayList to LinkedList in Java
Java Program to Reverse a linked list
Java Program to search an element in a Linked List
Anagram Program in Java
Inheritance Program in Java
Even Odd Program in Java
Hello World Program in Java
If else Program in Java
Binary Search Program in Java
Linear Search Program in Java
Menu Driven Program in Java
Package Program in Java
Leap Year Program in Java
Array Programs in Java
Linked List Program in Java
String Programs in Java
Star Program in Java
Number Pattern Program in Java
For Loop Program In Java
Pattern Program in Java
String Palindrome Program in Java
Thread Program in JAVA
Java Scanner Program
While Loop Program in Java
Bubble Sort Program in Java
Fibonacci Series Program in Java
Calculator Program in Java
Fizzbuzz Program in Java
Matrix Program in Java
Stack Program in Java