Recursion in Java

Recursion refers to the event when a function calls itself directly or indirectly. Recursion can be used at places where there is a certain relation between a sub-problem and the main problem, so sub-problems are solved individually, and solutions of all the sub-problems are combined to get the final result. In this article, we will understand the Recursion in Java and its applications.

What is Recursion in Java?

The process of making a function call itself is known as recursion. With the use of this strategy, complex problems can be reduced to more manageable, simpler ones.

Pseudo-code

Syntax

Output:

How Recursion Works?

Let us understand the working of recursion using a problem statement.

• You are asked to count the total number of people in the queue without leaving your place, where you are standing at first place in a queue of N number of people.
• You turn to look behind you to check if anyone is there. If not, you can respond with "0" as your response. Repeat this action if someone is present, then watch for their response as you stand back.
• After receiving a response, a person adds 1 for the person behind them before answering the questioner or the person in front of them.

The picture below shows how recursion works. At each recursive step, some computation is performed

Code for counting the total number of persons.

Output:

Explanation:

• As we can see in the above code snippet, the count function is calling itself. The above program runs until the number is not equal to the number assigned to the first person.
• Everytime we call the recursive function we decrease the counter of currentPerson by one and increase the counter of countTillNow by one.

Java Recursion Programs

1. Infinite recursion

Infinite recursion occurs only when the base case is not achieved or is not defined. In such cases, the recursive calls are made to themselves, and this leads to a stack overflow error.

Code

Output

Explanation

When we make a call to the print function, it will continuously call itself because no base case is applied, and hence it runs infinitely.

2. Palindrome Program in Java Using Recursion

Let us see a program to check whether the number is palindrome or not using recursion in Java.

Code

Output:

Explanation:

• In the above example, we first took a number and passed it into a function called palindrome. We have converted an integer number to a string in the palindrome function.
• Now we pass the string into the checkPalindrome function. The checkPalindrome takes three arguments, i.e., the input string s, left pointer, and right pointer.
• The recursive function checkPalindrome traverses the string from both sides, from left and right. We provide two base cases.

3. Factorial Program in Java Using Recursion

Let us write a program to find the factorial of a number using recursion in Java.

Code

Output

Explanation

• In the above code, the recursive function factorial takes an integer as a parameter. The base case for the factorial function is: if the value of n is zero, then return 1.
• If the value of n is not zero, then call the factorial recursively and decrease the value of n by 1.
• We are returning n * factorial(n - 1) because the factorial of a number x will be the product of x and the factorial of x-1. x! = x * (x - 1)!.

4. Fibonacci Series in Java Using Recursion

Let us understand the Fibonacci series by an example. Let us generate the Fibonacci series using recursion in Java.

Code

Output

Explanation

• In the above code, the recursive function fibonacci takes an integer as a parameter. The base case for the fibonacci function is: if the value of n is greater than or equal to zero, then return n.
• If the value of n is not zero, then call the fibonacci function recursively. We make recursive calls as fibonacci(n-1) + fibonacci(n-2) because F(n) = F(n - 1) + F(n - 2).

5. Binary Search Using Recursion

Code

Output

Explanation

In the above code, the binarySearch function takes four parameters, i.e., array, left pointer(l), right pointer(r), and the key element to be found(num).

Stack Overflow Error in Recursion

Let us understand the stack overflow error from the example taken above, i.e., finding the sum up to 20. We have defined the base condition; if the value of i is equal to 1, then it returns 1, and hence recursion will break or else recursion continues. What if we replace the base condition with the following code:

Output:

After executing the program, it will display a stack overflow error as recursion will never reach the base case because we decrease the value of i by 1 every time. Hence call stack memory will get exhausted by these method calls, and an error occurs.

Advantages of Recursion

• Writing iterative approaches is quite a difficult task as it requires a lot of implementation, whereas recursive approaches are very small to code.
• It is very useful in traversal techniques (Depth first search, Breadth first search, Inorder/Postorder/Pre-order tree traversals, etc.) where normal iteration is hard to implement.

Disadvantages of Recursion

• It is very difficult to trace recursion, which is why it is very hard to debug.
• Recursion uses a lot of stack memory as well as processor time.
• The machine may run out of memory if recursive calls are not written properly.
• It is hard to understand the code, as visualizing it is a tedious task.