In this article, we will learn about what is finite and infinite recursion in java. We will also see some sample examples which will help us to understand this topic more clearly.
Table of contents
When a function calls itself until a specified or base condition is met is known as recursion.
Infinite recursion
When a function calls itself again and again without any base condition is known as infinite recursion.
In case of infinite recursion, the function will execute infinite times till it runs out of memory and then throws a StackOverflowError.
package com.getinputs;
public class InfiniteRecursion {
static void print() {
System.out.println("Suraj");
print(); // recursive call
}
public static void main(String[] args) {
print();
}
}
Output: Suraj gets printed infinite times and then
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.UTF_8$Encoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io.OutputStreamWriter.write(Unknown Source)
at java.io.BufferedWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at java.io.PrintStream.println(Unknown Source)
at com.getinputs.InfiniteRecursion.print(InfiniteRecursion.java:7)
at com.getinputs.InfiniteRecursion.print(InfiniteRecursion.java:9)
StackOverflow error
We will see how the above example works
1. The main method calls the print method
2. print method prints ‘Suraj’ and calls print method again ( we will add the current print method to a stack since it is not complete )
3. First recursion – print method prints ‘Suraj’ and calls print method again ( we will add the current print method to a stack again since it is not complete )
4. Second recursion – print method prints ‘Suraj’ and calls the print method again ( we will add the current print method to a stack again since it is not complete )
5. This cycle goes on and on infinitely because we don’t have any condition which will stop these recursive calls and our stack keeps on increasing.
6. At one point the stack will reach its memory limit and our program stops abruptly throwing StackOverflow error.
Note* The waiting function will be stored in a stack.
Finite recursion
When a function calls itself with a base condition is known as finite recursion or just recursion. Here we will not get StackOverflowError.
package com.getinputs;
public class FiniteRecursion {
static int counter = 0;
static void print() {
if (counter == 3) {
return;
}
System.out.println("Suraj");
counter++;
print();
}
public static void main(String[] args) {
print();
}
}
Output : Suraj
Suraj
Suraj
Here ‘Suraj’ gets printed 3 times because we have added a base condition that terminates the recursive call if the counter reaches 3.
We will see how the above example works
1. The main method calls the print method
2. print method checks if counter == 3 since the counter is 0 hence it skips the if condition
- prints ‘Suraj’
- increment the counter by 1 ( counter is 1 )
- calls the print method ( the current print method will be added to the stack since it is not complete )
3. First recursion – print method checks if counter == 3 since the counter is 1 hence it skips the if condition
- prints ‘Suraj’
- increment the counter by 1 ( counter is 2 )
- calls the print method ( the current print method will be added to the stack since it is not complete )
4. Second recursion – print method checks if counter == 3 since the counter is 2 hence it skips the if condition
- prints ‘Suraj’
- increment the counter by 1 ( counter is 3 )
- calls the print method ( the current print method will be added to the stack since it is not complete )
5. Third recursion – print method checks if counter == 3 since the counter is 3 hence it goes inside if condition and returns. It completes the third recursive call and the pointer goes back to the second recursive call.
6. Since the print was the last statement in the second recursive call hence it completes, removes the print method stack entry and the pointer goes to the first recursive call.
7. Since the print was the last statement in the first recursive call hence it completes, removes the print method stack entry and the pointer goes to the main.
8. Since the print was the last statement in the main method hence the program completes and removes the print method stack entry.
So this is all about finite and infinite recursion in java. I hope you found this article interesting and valuable. If you are having any concerns or questions about this article please comment below and please share it to help me grow.