Recursion in Java

Recursions are techniques for calling a function on its own. This method enables complex problems to be solved in simpler ways so that they can be dealt with more easily. It may be hard to understand how the incursion was carried out. Experimenting with it is the best way of knowing how it works.

What is Java Recursion

Recursion is a process in Java where a function calls itself directly or indirectly, and the corresponding function is called a recursive function. Some problems may be solved relatively quickly with the use of an infinite recursion algorithm.

Java Recursion Example:

It is easy to add two numbers together, but it can be more difficult to add a whole series of numbers. Recursion is used to add a number of numbers together, breaking these into simple tasks such as the addition of two:

Example:

Use recursion to add all of the numbers up to 10.

public class TechVidvan {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

Example Explained:

When calling the sum() function, a parameter k is added to the sum of all numbers smaller than k, and the result is returned. The function will only return 0 when k is 0.

Java Recursion Programs

1. Factorial Using Recursion:

The computation of the factorial of a number is a classic example of recursion. All the numbers between 1 and N form the factorial of the number N. The factorial values of the numbers 3, 4, and 5 shall be calculated using the given code.

3= 3 *2*1 (6)
4= 4*3*2*1 (24)
5= 5*3*2*1 (120)

Base Condition in Recursion:

The recursive program provides a solution to the initial case, and the solution to the larger problem is expressed in terms of smaller problems.

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

In the above example, the base case for n < = 1 is defined, and the larger value of a number can be solved by converting it to a smaller one till the base case is reached.

Working of Recursion:

It is intended to represent a problem in the sense of one or more smaller subproblems, which can be supplemented by base conditions that will prevent recursion. For example, if we know the factorial of n-1), then we can compute a factorial N. A factorial base case would be n = 0. If n is 0, we’ll return 1

How is memory allocated to different function calls in recursion?

• The memory for each function is allocated to the stack as soon as they are called from main().
• A recursive function calls itself, the memory for the called function is allocated on top of the memory allocated to the calling function, and a different copy of local variables is created for each function call.
• The function will return its value to the function by which it is named, and memory will be deleted when a baseline case has been established, then proceed as normal.

Advantages of Recursive Programming

• Recursion allows you to write code in a clean and easy way. There are certain problems, such as a tree traversal or the tower in Hanoi, which are inherently recursive.
• It is better to write recursive code for this kind of problem.

Disadvantages of Recursive Programming

• Recursive programs have more of a space requirement than iterative programs because all functions will be in the stack until they reach their base case.
• Due to function calls and returned overheads, it also requires more time.

We call Recurse() from the main method, as shown below. (normal method call). And this time, we’re calling a similar recurse method in the Recurse() method. This is a recursive call.

• There are certain conditions in the method that need to be met before we can stop a recursive call. If this is not the case, the method will be called infinitely.
• Thus, in order to end a recursive call inside this method, we are using the if…else statement reflexively.

Types of Recursions in Java

Recursion is essentially two types, depending on whether a function calls itself from within it or several functions call one another in turn. There are two kinds of direct recursions; one is called Indirect Recursion, and another is called Direct Recursion.

It follows that there are two types of recursion:

1. Direct Recursion:

Tail Recursion: If a recursive function calls itself and this recursive call is the final statement in that function, then it’s called Tail Recursion. There is no performance of the recursive function after this call. At the time of the call, the function must process or perform any operation, and at the time of the return, it does not perform any operation.

To understand an example, we need to trace a recursion function tree. This means the calls and outputs will be issued in this way.

Time Complexity For Tail Recursion: O(n)
Space Complexity For Tail Recursion: O(n)

Head Recursion: When a recursive function calls itself, and when that recursive call is the first statement of this function, it’s called Head Recursion. Before the call, there is no statement. There are no operations. The function doesn’t have to process or perform any operation at the time of calling, and all operations are done at returning time.

Tree Recursion: Let us first understand the Linear Recursion to get a good understanding of tree recursion. It is known as linear recursion if recursive functions call themselves for one time. In other words, if you have a recursive function calling itself more than once, it’s called the Tree Recursion.

2. Indirect Recursion:

There may be more than one function in that recursion, which calls each other back and forth.

From the diagram above, fun.A calls fun.B, fun.B calls fun.C, and fun.C calls fun.A, thus making a cycle.

Conclusion

Recursion is an efficient way to solve different programming problems, which can lead to elegant solutions. However, it should be applied with a thorough understanding of the basic case and its possible consequences for memory.