What is Recursion In Java programming – Here we cover in-depth article to know more about Java Recursion with proper examples.
What Is Recursion?
- Recursion is a process of a method calling itself.
Eg:
1 2 3 4 5 6 7 8 9 |
void meth() { //some statements meth(); //recursive call (a method calling itself) //some other statements } |
In the above example, a method is calling itself directly. In some cases a method may call itself indirectly (through some other method).
Eg:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void meth1() { meth2(); } void meth2() { meth1(); } |
In Java, recursion is allowed through normal methods but not allowed with constructors. So the following code is not valid (assume class name is Check, so constructor name is also Check).
Eg:
1 2 3 4 5 6 7 8 |
Check() { this(10); } Check(int x) { this(); } |
Even direct recursion is also not allowed with constructor calls. So the following code is also not valid.
Eg:
1 2 3 4 5 6 7 |
Check() { this(); } |
Even though recursion with constructor calls is not allowed, we can make recursion with normal methods even though they are initiated at constructors. So the following code is valid.
Eg:
1 2 3 4 5 6 7 8 9 10 11 12 |
Check() { meth(); } void meth() { //some code meth(); } |
When recursion takes place, a method is invoked again and again. If we don’t stop the repetition, then it becomes infinite callings and the program never ends. An example of such is given below.
Example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Check { public static void main(String arg[]) { nums(1); } static void nums(int x) { System.out.print(x+" "); nums(x+1); } } |
Output:
1 |
1 2 3 4 5 6 ………….(indefinite) |
- In the above program, main() is invoking nums() with argument 1.
- This 1 comes to the method nums() into x. there 1 is printed.
- Then nums() invokes itself with x+1 as argument.
- It means 2 is passed this time to nums() as argument and x receives 2.
- So 2 is printed, and then nums() is called with value 3.
This process continues without any stoppage. So the program keeps executing. If we want to stop the execution, we can do so with Ctrl+C (from windows command prompt) or the program may be terminated by the system itself as it has become infinite (memory shortage).
Recursion is a very good mechanism in many cases. But, this kind of (infinite) recursion is not much useful. If we can control the recursion so that it can be stopped by the programmer (programmatically/logically/technically) at a desired point then it would be better.
The above program is written here with some modifications so that it stops at a stage.
Eg:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Check { public static void main(String arg[]) { nums(1); } static void nums(int x) { System.out.print(x+" "); if(x==3) return; nums(x+1); } } |
Output:
1 |
1 2 3 |
In the above program, the method nums() has 3 statements.
- out.print(x+” “);
- if(x==3) return;
- nums(x+1);
When control comes to a method, it returns (goes back) to the calling method in 2 situations.
- When a return statement is executed.
- When all the statements in the method are completed execution.
Keep in mind, when we call a method recursively, the same method is called many times and such version will be referred as one version.
It means, when nums() is called for the first time, let us refer is as first version and when the same method is called for second time, let us refer it as second version and so on.
Note: Each time the control comes to a new version of a method, all local variables of it are created afresh.
When recursion is used, we should see the following two things are happening in the recursive method.
- A terminating condition (so that the recursion stops)
- Moving towards starting stage to terminating stage.
The above example of printing natural number can be written without using recursion also. In that case we just use a looping/iterative construct. Which one is better?
Similarly we can write a program to print factorial of a number in non-recursive (iterative) way as well as recursive way. Which one is better?
- We can write a program to find GCD of given two numbers. Recursive is better or non-recursive?
- For writing a quick sort program, what should we choose? Recursive or non-recursive?
- for a merge sort, should we approach recursive or non-recursive?
- For travelling a single-linked list in forward direction which is better?
- For printing a single-linked list in backward direction (from last one to first one) what is better?
- For travelling a tree in pre-order, post-order, in-order and level-order, which one is better?
For all these questions, one principle we should keep in mind. If we can write a program without an exclusive stack, then non-recursive (iterative) one is better.
As a replacement to exclusive stack (recursion inclusively forms a stack) usage, we should approach recursion. So the programs like printing natural numbers, factorial of a number, GCD of numbers, single linked-list forward traversal, tree level-order traversal can be done non-recursive way.
But recursion is very much useful for writing programs like quick sort, merge sort, travelling single-linked list in backward direction, pre-order post-order and in-order traversals of tree, towers of Hanoi, graph traversals.
To find factorial of a number, we just can use a loop and find the result. In this case we do not need a stack to store intermediate data and then used it at a later stage.
But in quick sort, we need to store data at each level and use it at a later stage. For the storage we need a stack. So we should implement a stack also along with quick sort. If we approach a recursive method, we need not to maintain a stack. So for writing quick sort program, a recursive one is better.
If we want to use multiple recursive calls in a method (a method calling itself more than one time) then the mechanism will be little bit complex. But it helps us solving many problems, otherwise we need to write a lot of code ( to maintain stack, pushing, popping, etc ). This kind of approach is used in ‘divide and conquer’ methodologies like quick sort and merge sort.
Java Recursion Examples With Sample Programs
Example: 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class RecursionExample1 { public static void main(String args[]) { int i=5; RecursionExample1.print(i); } static void print(int i) { if(i>0) { print(i-1); System.out.println(i); } } } |
Output:
1 2 3 4 5 |
1 2 3 4 5 |
Example:2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class RecursionExample1 { public static void main(String args[]) { int i=5; RecursionExample1.print(i); } static void print(int i) { if(i>0) {System.out.println(i); print(i-1); } } } |
Output:
1 2 3 4 5 |
5 4 3 2 1 |
Drawbacks/Limitations/Disadvantages Of Recursion
- As too many number of method calls takes place, memory allocated for local variables may occupy too much of memory.
- The allocation of resources for these many versions of methods slows down the performance.
- An average programmer feels difficult to understand the working of recursion.