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.