Recursion in Java

In this article, we will examine the concept of recursion in Java. We will first investigate what recursion is, how it works, its necessity, and its advantages and disadvantages.

In the end, we will look at different examples of recursion using programs to better understand their function. To grasp the concept more quickly and master it, I suggest you practice each code snippet in the article, make modifications, and tinker with it to cover different scenarios.

What do you mean by recursion in Java?

Recursion is a programming technique in which a function calls itself directly or indirectly. It is a powerful tool for solving complex problems.

In Java, recursion is implemented using the return statement. When a function calls itself, the value of the variables in the calling function is preserved.

This allows the function to continue executing from where it was called. Recursion can solve problems such as factorials, Fibonacci numbers, and finding the nth Fibonacci number.

What are the benefits of implementing recursion in Java?

Recursion can be used to solve problems that would be difficult or impossible to solve with other programming techniques.

Some of the advantages of recursion in Java include:

1. It can be used to write concise and elegant code.

2. It can solve problems that other programming techniques find difficult or impossible.

3. It can be used to create recursive data structures, which can be very efficient for storing and manipulating data.

4. It can be used to create recursive algorithms, which can efficiently solve problems.

However, recursion can also be challenging to understand and debug. It is essential to be careful when using recursion, as it can lead to infinite loops if not implemented correctly. That brings us to the next section:

What are the disadvantages of using recursion in Java?

Recursion has a lot of benefits; however, there are some disadvantages to using recursion:

1. Recursive calls and automatic variables are stored on the stack, which consumes more storage space. If recursive calls are not checked, the computer may run out of memory.

2. It is not more efficient in speed and execution time. Some computer professionals say recursion offers no concrete advantage over non-recursive procedures/functions.

3. A recursive solution is often logical but difficult to debug and understand.

4. In recursive code, we must have an if statement somewhere that forces the function to return without executing the recursive call. Otherwise, the function will never return.

5. Recursion uses more processor time and is not advocated when the problem can be solved through iteration. Recursion is a powerful programming technique, but it should be used with care.

What are the properties of a recursive function?

Whenever you write a recursive function, you should make sure you satisfy these 3 rules or properties:

1. A recursive solution must contain a base case.
2. A recursive solution must contain a recursive case.
3. A recursive solution must make progress toward the base case.

You may ask, ” What is a base case?” The base case is the terminating case and represents the smallest subproblem. It indicates the end of the virtual loop or recursive calls.

Each recursive call should bring you closer to a situation where the answer is known. Each recursive algorithm must have at least one base and a general (recursive) case.

A base case is when the algorithm can stop recursing and return a known answer. The general case is when the algorithm needs to call itself to solve a smaller problem.

How does recursion work in Java?

The workings of recursion might be a little intimidating at first, but let us take an example and use diagrams to understand it better. Let us consider the simple problem of printing the integer values from 1 to n in reverse order. The iterative solution for this problem is relatively simple when using a loop construct. But it can also be solved recursively:

void printRev(int n)
{
if (n>0)
{
System.out.println(“%d”,n);
printRev(n-1)
}
}

In printRev(), the base case occurred when n = 0, and the function returned without performing additional operations. Subdivision is handled by the recursive case, in which the function calls itself. In the printRev() function, the recursive case is performed for all values of n > 0.

A recursive solution must progress toward the base case, or the recursion will never stop, resulting in an infinite virtual loop. This progression typically occurs in each recursive call when the larger problem is divided into smaller parts.

Each recursive call subdivides the larger data set into smaller sets or reduces the larger term to a smaller value. In our recursive printing solution, this progression is accomplished by subtracting one from the current value of n in each recursive function call.

Let us look at a diagram to understand how the recursion in the function shown above works.

Memory allocation is different for different function calls.

When a function is called from main(), its memory is allocated on the stack. In the context of recursive functions, a function invokes itself, causing the memory for the called function to be allocated on top of the memory allocated for the calling function. This results in separate local variable instances for each recursive call. Upon reaching the base case, the function returns its value to the calling function, triggering memory deallocation, and the recursive sequence progresses.

What are the different types of recursion in Java?

There are 2 types of recursion:

Direct and indirect. Let us take a look at them in detail with the help of examples:

Direct recursion in Java

A method is directly recursive when it calls itself in its body.

Here is the general syntax of a direct recursion:

Def function1(p1, p2, …, pn):
{
    <statements>
    function1(p1, p2, …, pn)
    <statements>
}

Indirect recursion in Java

Indirect recursion (or mutual recursion) occurs when a function calls another function, eventually resulting in the original function being called again.

For example, if function1() calls function2() and function2() eventually calls function1(), this results in indirect recursion (or mutual recursion).

Here is pseudocode illustrating indirect recursion:

Def function1(p1, p2, …, pn)
{
    <statements>
    function2(p1, p2, …, pn)
    <statements>
}
Def function2(p1, p2, …, pn)
{
    <statements>
    function1(p1, p2, …, pn)
    <statements>
}

Examples of recursion in Java

Now that we know recursion inside out, let us look at some examples to see it in action!

Factorial of a number using recursion in Java

public class FirstCode 
{
  public static void main(String args[]) 
  {
    long nFactoriral = factorialProgram(10);
    System.out.println(nFactoriral);
  }
  public static long factorialProgram(long n) 
  {
    if (n <= 1) {return 1;}
    else {return n * factorialProgram(n - 1);}
  }
}

Output:

3628800

Printing the first 10 numbers of the Fibonacci sequence using recursion in Java

public class FirstCode 
{
  public static void main (String args[]) 
  {
    for(long i=1; i<=10; i++){ 
      System.out.print(fibonacci(i) +" "); 
    }
    System.out.println();
  }
  public static long fibonacci(long number) 
  {
    if (number == 1 || number == 2) {return 1;}
    return fibonacci(number - 1) + fibonacci(number - 2);
  }
}

Output:

1 1 2 3 5 8 13 21 34

Printing the sum of a series using recursion

public class FirstCode 
{
  public static void main(String[] args) 
  {
    long sumOfAllNumbers = sumOfAllNumbers(10);
    System.out.println(sumOfAllNumbers);
  }
  public static long sumOfAllNumbers(long number) 
  {
    if (number != 0) {return number + sumOfAllNumbers(number - 1);}
    else {return number;}
  }
}

Output:

55

What is the difference between recursion and iteration in Java

Before we call it a day, let us take a moment to look at the differences between iteration and recursion:

Parameter	Recursion	Iteration
Defintion	In recursion, a function calls itself, either directly or indirectly.	Here, a set of instructions is executed repeatedly
Area of application	Recursion is used in functions	Iteration is used in loops
termination	Recursion terminates at a base case, where there are no function calls.	Iteration terminates when the iterator’s termination condition is satisfied.
When is it used?	Recursion is used when the code size needs to be small, and the time taken is not essential.	Iteration is used when time complexity needs to be balanced against an expanded code size.
Time complexity factor	Very high	Lower than recursion
Space complexity	Higher	lower
Performance	Slow execution	Faster execution
Memory	More utilization	Less utilization
Usage of the stack	Uses stack	Does not use a stack

Conclusion

You have now learned everything there is to know about the concept of recursion in Java. We have gone through various topics, including its definition, advantages and disadvantages, properties, working, a diagram, and the 2 types of recursion. In the end, we also saw a couple of examples of recursion in action and discussed the differences between iteration and recursion based on various parameters.