When we call a function from its own body, it is known as recursion and the function is called a recursive function. The most relevant example of recursion in real life will be two parallel mirrors facing each other. Java supports recursive function calls.
The call may be direct or indirect; usually, when more than one function is involved, the call is considered to be indirect. If the recursive call is made implicitly, we call it “anonyms recursion.”In recursion, we use a stack store, all the called functions.
Most of us are familiar with functions; they can be defined as blocks of code that are executed only when they are called. The primary advantage of a function is that it ensures code re-usability. Functions can be both in-built or user-defined.
The implementation of a function involves three main steps: Function declaration, function definition, and function call. The return type of a function must also be specified while declaring it.
A stack is a data structure that follows the LIFO implementation. This means that the last function call will be executed first, and the return value will be stored until all the functions present in the stack are cleared. The graph traversal problems are best handled with the help of recursion.
Writing recursive functions reduces the time complexity of code significantly and also reduces the developer’s time required to write and debug the code.
However, recursion increases the overall space complexity of a thread, As all the function calls have to be stored in a stack, and during execution, the returned value from each function also adds to the memory requirements. For each recursive problem, there is an iterative alternate.
The basic arithmetic programs that are used for learning recursion are the Fibonacci series, power of a number, factorial of a number, etc.
Some problems in which recursion is used conventionally are searching and sorting algorithms, Breadth-first search, Tower of Hanoi, Graph traversal strategies: In-order, Pre-order, and Post-order, etc.
Read more, how to run java program
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:
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