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 CodeIn 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.