How Recursion works in Java with example

How Recursion works internally in Java

---

In this post, we will see, how recursion works internally in java with example along with recursive function practice programs in Java.
We will also see, how Stackoverflow error is caused in Recursive functions.

What is Recursion?

---

Recursion is a process in which a function gets called repeatedly, either directly called by the same method or via other method call and such a method is called Recursive function.

To keep it simple, I would say, when a function calls itself is called recursion or a recursive call. Let's understand recursive function with a small example,

What is Base condition in recursion?

---

We have seen in recursion a function calls itself, now if the function keep calling itself recursively then how the control is going to come out, that is where a Base condition helps. Base condition is a necessary check to break the recursive call at some point.

Which data structure is used internally in recursion?

---

Stack data structure is used in recursion for storing the state of each function call.

Explain the use of stack in recursion?

---

let us first understand why we need data structure in recursion. check below program to find factorial using recursion in java

 
private static int findFactorialRecursive(int num){
   if(num < 0) {
     return -1;
   }
   if(num == 1 || num == 0) {
     return 1;
   }
   num = num * factRecursive(num-1); //Recursive call
   return num; 
}

When above function is invoked for the first time, method would be executed till line number 8, and post that it would jump back to line number 1 for a fresh method call with a new value of “num”.

If a function will execute again(second time) with new value of num, what about the value of previous num as it still has to execute line number 9 of the first call and has to preserve the value of num( basically it has to preserve state of first method call, then second call, then third call and so on).
So when a function calls itself, Stack is used to store the state of previous call.

Lets understand how recursion works internally with recursive call stack diagram.

Recursive call stack diagram

Recursion practice programs with solution

---

List of recursive practice programs, some of the recursive programs are tricky, read the complete solution to understand it better.

1. Factorial of Number using Recursion in Java
2. How to Reverse Word in Java Recursively
3. Find Power of a Number using Recursion in Java
4. Reverse String in Java using Recursion
5. Tower Of Hanoi Recursive solution
6. Implement Queue using Stack - Recursion.
7. Reverse linked list using recursion in Java
8. Print Linked List In Reverse Order using Recursion in Java
9. Print Matrix in Spiral order using Recursion
10. Fibonacci series in java using recursion
11. Find Power of a Number using Recursion in Java

When Stackoverflow error is caused by recursive function?

---

In recursion, a method calls itself and a Stack data structure is used internally to store the state of each function call.

So as long as the function keep calling itself, Stack memory needs to be allocated for each function call.

Consider a situation where a program never hits the base condition then function will keep calling itself and Stack memory consumption will keep on increasing and at one point when there would be no Stack memory left to allocate for the next function call at that time Stackoverflow error would be thrown.

You may also like to see

---

Command Design Pattern

Observer Design Pattern

Adapter Design Pattern

Decorator Design Pattern

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Read more

Find length of the longest valid parenthesis substring

Find length of the longest balanced parenthesis in a string.

---

Given a string consisting of opening and closing parenthesis, find the length of the longest balanced parenthesis in it.

Lets see sample input and output for better understanding:

longest valid parentheses count

Read more

Sort a Stack using Merge Sort

Sort a Stack using Merge Sort.

---

Lets see how to sort a stack using merge sort which uses divide and conquer recursive algorithm.

I recommend reading Merge sort first before proceeding.

Also, check Merge sort article on linked list that will help in understanding Merge sort and this article better.

Lets see sample input and output for better understanding:

Sort a Stack using Merge Sort in Java

Read more

BFS vs DFS with Example in Java

BFS vs DFS with Example

---

Breadth First Search(BFS) Vs Depth First Search(DFS) with example in Java. DFS uses Stack while BFS uses Queue.

Given two words, startWord and endWord, and a dictionary, find the length of shortest transformation sequence from startWord to endWord.
Rules:
1. Only one letter can be changed at a time.
2. Each intermediate word must exist in the dictionary.

Input
startWord     = CAT
endWord      = DOG
dictionary    = CAT, BAT, COT, COG, COW, RAT, BUT, CUT, DOG, WEB 

Output
One shortest transformation is CAT –> COT –> COG –> DOG.
the program should return Path and its length 4.

Let's look at few more example and better understand problem statement.

There can be many paths for reaching from startWord to endWord, but we have to find shortest path possible.

Read more

Implement Queue using One Stack in Java (Recursive Implementation)

Implement Queue using One Stack in Java

---

You are given a Stack data structure that supports standard push and pop operations. You need to implement Queue data structure using one Stack instances.

Lets understand the problem statement graphically and it will be more clear,  

Read more

Implement Queue using Stack

Implement Queue using Stack in Java

---

You are given a Stack data structure that supports standard push and pop operations. You need to implement Queue data structure using Stack instances.

Lets understand the problem statement graphically and it will be more clear,  

Read more

Implement Stack using One Queue

Implement Stack using Single Queue in Java

---

You are given a Queue data structure that supports standard enQueue and deQueue operations.  You need to implement Stack data structure using Single Queue.

Lets understand the problem statement graphically and it will be more clear, 

Read more

Implement Stack using Queue

Implement Stack using Queue in Java

---

You are given a Queue data structure that supports standard enQueue and deQueue operations. 
You need to implement Stack data structure using Queue instances.

Lets understand the problem statement graphically and it will be more clear, 

Read more