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 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 fist, 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.
There are 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 as 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 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
case is reached. After each function call, there should be an appropriate change in the parameters, based on our requirement. We must analyse 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 are 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 the reverse
order as the stack uses the LIFO approach. The number of recursive calls should be minimised,
as a higher number of recursive calls required 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 code, depending upon the problem
Types of Recursion:
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 categorised 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.
int head_recur(int n)
//The function begings with a recursive call
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.
int tail_recur(int n)
//The function ends with a recursive call
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
Recursive V/S iterative Approach:
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.
Recursive codes have a higher space complexity than the iterative codes of the same problem.
Each function call and its return value is 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.
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 also.
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.
When it comes to computational power, the recursive and iterative approach, both stand in the
same place. Both have the capability to solve any problem if coded logically.
If recursive algorithms are not well designed, they made lead to StackOverflow. They have a higher tendency to cause system failure than iterative codes.
To read more about Java, click here.
By Vanshika Singolia