Table of contents
1.
Introduction
2.
What is Recursion in Java?
3.
Three main steps for implementing recursion:
3.1.
Step One: Base case generation
3.2.
Step Two: Problem-solving methodology
3.3.
Step Three: Recursive Call
4.
Types of Recursion in Java:
5.
Recursive V/S iterative Approach:
5.1.
Time Complexity
5.2.
Space Complexity
5.3.
Code Clarity
5.4.
Debugging
5.5.
Output
5.6.
System Malfunctioning
6.
Example of Recursion in Java
7.
Frequently Asked Questions
7.1.
How do you code recursion?
7.2.
What is recursion with an example?
7.3.
What is recursion in language?
7.4.
What is recursion used for?
7.5.
What is recursive thinking?
7.6.
What is recursion syntax?
8.
Conclusion
Last Updated: Oct 28, 2024
Medium

Recursion in Java

Author
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Recursion occurs when a function calls itself, either directly or indirectly, a method supported by Java. This technique utilizes a stack to manage function calls, adhering to a last-in-first-out execution sequence. Recursion is particularly useful in simplifying complex tasks such as graph traversal and algorithmic problems like searching and sorting. While it can reduce time complexity and ease development, it also increases space complexity due to the accumulation of function calls in the stack.

What is Recursion in Java?

Recursion in Java is a programming technique where a method calls itself to solve a problem. It's an approach often used when a problem can be divided into similar subproblems. The method that performs this self-call is known as a recursive method.

A recursive method must have a base condition to terminate the recursion; otherwise, it can lead to an infinite loop, eventually causing a stack overflow error because each recursive call uses some space on the stack. This base condition checks for simple, solvable instances of the problem, which do not require further recursion.

Java supports both direct and indirect recursion. Direct recursion occurs when the method directly calls itself, while indirect recursion involves multiple methods calling each other in a cycle.

Recursion is commonly used for tasks like calculating factorials, processing tree structures (such as XML parsers or file system explorers), and implementing algorithms for searching and sorting, among other uses. The simplicity of expressing certain algorithms recursively often makes the code more readable and shorter, though it might not always be the most efficient in terms of space and time complexity compared to iterative solutions.

Three main steps for implementing recursion:

Step One: Base case generation

We provide the solution of the smallest possible input and express the higher inputs in terms of the smaller cases. The terminating case is known as the base case. For one code, there can be more than one test case. We break large problems into multiple smaller problems. We compute the final result by combining the output of all the problems that we store in the stack. While choosing the base case, we must keep in mind that it should be reachable. If the base case is not reachable, infinite function calls will be stored in the stack, and stack overflow will take place, and ultimately our thread will be dumped, or the system will crash. If the base case is incorrect the test cases will fail, hence this step must be carried out with utmost care.

For Example: To find the nth Fibonacci term (0,1,1,2,3,5,8…….)
We use the formula:
Fib(n)=Fib(n-1)+ Fib(n-2)
To compute the 3rd term of the series, we can add the first and second terms. Therefore, we need the value of the first two terms to compute the series. We have to provide a solution for n=0 and n=1. Here,n=0 and n=1 are the base cases.

Step Two: Problem-solving methodology

Like in the problem of Fibonacci numbers, we used the addition operator to combine the outputs and the decrement operator to change the value of the parameter. We assume that some part of the solution will be given by recursion, and for the remaining part, we have to write the code in the function’s body. A problem-solving algorithm must be constructed logically so that the output is according to our requirements. Most of these algorithms are based on the principle of mathematical induction that, if a statement says P(n) is true for n=1,n=k, and n=k+1, then it is true for all values of n. Generally, first, a recurrence relation is created, and then it is implemented using programming languages.

A relationship between the base case and the higher values must be derived so that the base
the case is reached. After each function call, there should be an appropriate change in the parameters, based on our requirement. We must analyze which parameters require a change. It is not mandatory to change all the parameters. Always dry run the code using some test cases to check the logic or presence of bugs. We have to include constraints for handling duplicates and exceptions. In some cases, the recursive call is made first, whereas, in others, the calculation part is done first. The order of the steps is totally specific to the problem statement and the output required.

Step Three: Recursive Call

The recursive call should be necessarily made to call the function again. A recursive call can be made in two ways: from the function itself, directly or by using a helper function, indirectly. The recursive call is made multiple times till the base is reached. All the recursive calls made are stored in a stack, in the order in which they are called.

The return value is given in reverse order as the stack uses the LIFO approach. The number of recursive calls should be minimized, as a higher number of recursive calls requires higher stack memory. We must make sure that our code doesn’t lead to an infinite number of recursive calls. There are some codes that end with a recursive call. They can be placed anywhere in the code, depending on the problem statement.

Also see,  Eclipse ide for Java Developers

Types of Recursion in Java:

As mentioned already, recursion is of two types, namely direct and indirect recursion. Indirect recursion is also known as mutual recursion. Direct recursion can be categorized into six different types, depending upon the number or position of the function call:

Linear Recursion: In linear recursion, each function calls itself once only.
Example: Linear Search, Power of a number, Print n numbers, factorial of a number, etc.

Binary Recursion: In binary recursion, each non-base case calls the function twice.
Example: Search In a Binary Search Tree, Fibonacci numbers, etc.

Tree Recursion: In Tree recursion, each function calls itself multiple times. The parameters of each call are generally different.
Example: Searching an element in a Generic Tree Tree, Merge Sort, Quick Sort, etc.

Head Recursion: With respect to the order of statements in a function, if the recursive call is the first statement of the code, it is said that you have implemented head recursion.

Example:
int head_recur(int n)
{
if(n=0)
{
//The function begings with a recursive call
head_recur(n-1);
}
System.out.printf(n);
}

Tail Recursion: With respect to the order of statements in a function, if the recursive call is the last statement of the code, it is said that you have implemented tail recursion.
Example:
int tail_recur(int n)
{
if(n=0)
{
System.out.printf(n);
}
//The function ends with a recursive call
tail_recur(n-1);

}

Nested Recursion: It can be basically defined as “recursion within the recursion.”This signifies that one of the parameters of the initial recursive function is computed with the help of recursion. A separate function may be created for computing the values of the recursive parameters. Depending on the number of recursive functions, the number of stacks required is decided. The use of nested recursion should be minimised to reduce the memory application.
Example: Ackerman’s function, which shows us that total computable functions are not
primitive recursive.

Recursive V/S iterative Approach:

Time Complexity


Recursion reduces the time complexity of code significantly. When the rum time of the thread is
our priority, then we must use recursion only. Every iterative code can be converted into a recursive code. There are very few exceptions, in which we can’t write a recursive alternate for an iterative code.

Space Complexity


Recursive codes have a higher space complexity than the iterative codes of the same problem. Each function call and its return value are stored in the stack until the base case is reached. All this data requires a very high memory. If a proper base case is not reached, this may even cause a stack overflow, and core will be dumped. After the execution of a recursive function, the memory needs to be deallocated.

Code Clarity


Recursive codes are preferred over iterative codes as they are more concise. Generally, recursive codes are smaller than iterative codes in terms of LOC(Line of Code). This helps in-code documentation and maintenance.

Debugging

 
Recursive codes are easy to debug as they are well structured. They reduce the developer’s time significantly. Many times it happens that one developer writes the code, and the other updates it; using recursion helps in writing concise and easy-to-debug codes.

Output


When it comes to computational power, the recursive and iterative approaches, both stand in the same place. Both have the capability to solve any problem if coded logically.

System Malfunctioning


If recursive algorithms are not well designed, they may lead to StackOverflow. They have a higher tendency to cause system failure than iterative codes.

Also read, even number program in java

Example of Recursion in Java

public static int factorial(int n) {
   // Base case: factorial of 0 is 1
   if (n == 0) {
       return 1;
   }
   // Recursive case: factorial of n is n multiplied by factorial of (n-1)
   else {
       return n * factorial(n - 1);
   }
}
You can also try this code with Online Java Compiler
Run Code

In this example, the factorial method calls itself with n - 1 until the base case of n == 0 is reached. The factorial of a number n is calculated by multiplying n with the factorial of n - 1, and this process continues until the base case is met.

Frequently Asked Questions

How do you code recursion?

To see code in recursion, you can look up recursive functions in c, recursive functions in Python, recursive functions in Java, recursive functions in C++, or recursive functions in data structures in general.

What is recursion with an example?

Recursion is the phenomenon in programming where a function, called the recursive function calls itself directly or indirectly based on certain conditions.
Example:
void recursion(int n){
if(n==0) return;
else
recursion(n-1);
}

What is recursion in language?

Recursion in language is the phenomenon of repeating things in a way that seems similar to the parent thing.

What is recursion used for?

Recursion is used for breaking down a complex problem into a simpler problem.

What is recursive thinking?

Recursive thinking is the process of analyzing a problem and breaking it down into smaller problems.

What is recursion syntax?

Recursion syntax is the syntax of writing a recursive call which consists of the name of the recursive call and arguments if any.

Conclusion

In this article, we talked about recursion in Java. It's a way of solving problems by having a method call itself over and over until it reaches a specific condition. This can help solve tricky problems, but you have to be careful not to let the method keep calling itself forever. Recursion can make your code look neat, but sometimes using loops might work better.

Live masterclass