This post demonstrates how to limit the number of recursive calls to avoid StackOverflowError in Java.
Recursive method call
Recursive method call is invoking the method from within the same method. For example, these codes have a helloWorld() method that displays the text "Hello World" and calls the same method on line 4.
[wp_ad_camp_1]
1 2 3 4 5 6 7 8 9 10 11 | public class RecursiveCallDemo { public void helloWorld() { System.out.println("Hello World!"); this.helloWorld(); } public static void main(String... a) { RecursiveCallDemo demo = new RecursiveCallDemo(); demo.helloWorld(); } } |
If these codes are run, we get around ~2344 lines of text as shown below.
[wp_ad_camp_2]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | Hello World! Hello World! Hello World! Hello World! Hello World! Hello World! ... Hello World! Exception in thread "main" java.lang.StackOverflowError at java.io.FileOutputStream.write(FileOutputStream.java:326) at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.java:82) at java.io.BufferedOutputStream.flush(BufferedOutputStream.java:140) at java.io.PrintStream.write(PrintStream.java:482) at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221) at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291) at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104) at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185) at java.io.PrintStream.write(PrintStream.java:527) at java.io.PrintStream.print(PrintStream.java:669) at java.io.PrintStream.println(PrintStream.java:806) at RecursiveCallDemo.helloWorld(RecursiveCallDemo.java:3) at RecursiveCallDemo.helloWorld(RecursiveCallDemo.java:4) at RecursiveCallDemo.helloWorld(RecursiveCallDemo.java:4) ... |
Recursion is a very powerful concept that can simplify a solution to a problem. “Simplify” means the solution uses less codes, elegant, and concise.
Real-life Simple Example
Sample Data
On the left side, we have the levels of method calls.
- Level 1 has A
- Level 2 has A and B
- Level 3 has D, E, C1, and C2
- Level 4 has D1, D2, E1, and E2
For our purpose, we want to prevent the codes from going to level 3 and beyond.
[wp_ad_camp_3]
Our Existing Codes
Our simple example consists of 2 files – TwoSiblingsBean.java and TwoSiblingsDemo.java.
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 27 28 29 30 | package recursion; public class TwoSiblingsBean { private String name; private TwoSiblingsBean left; private TwoSiblingsBean right; public TwoSiblingsBean(String name) { this.name = name; } public TwoSiblingsBean getLeft() { return left; } public void setLeft(TwoSiblingsBean left) { this.left = left; } public TwoSiblingsBean getRight() { return right; } public void setRight(TwoSiblingsBean right) { this.right = right; } public String getName() { return name; } } |
[wp_ad_camp_4]
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | package recursion; public class TwoSiblingsDemo { public void recursion(TwoSiblingsBean bean) { System.out.println(bean.getName()); if(bean.getLeft() != null) { recursion(bean.getLeft()); } if(bean.getRight() != null) { recursion(bean.getRight()); } } public static void main(String[] args) { // Root TwoSiblingsBean b1 = new TwoSiblingsBean("A"); // Children of root b1.setLeft(new TwoSiblingsBean("B")); b1.setRight(new TwoSiblingsBean("C")); b1.getLeft().setLeft(new TwoSiblingsBean("D")); b1.getLeft().getLeft().setLeft(new TwoSiblingsBean("D1")); b1.getLeft().getLeft().setRight(new TwoSiblingsBean("D2")); b1.getLeft().setRight(new TwoSiblingsBean("E")); b1.getLeft().getRight().setLeft(new TwoSiblingsBean("E1")); b1.getLeft().getRight().setRight(new TwoSiblingsBean("E2")); b1.getRight().setLeft(new TwoSiblingsBean("C1")); b1.getRight().setRight(new TwoSiblingsBean("C2")); TwoSiblingsDemo demo = new TwoSiblingsDemo(); demo.recursion(b1); } } |
This outputs the following.
1 2 3 4 5 6 7 8 9 10 11 | A B D D1 D2 E E1 E2 C C1 C2 |
These codes went to level 3 and beyond.
Limit Recursive Calls
We could change the TwoSiblingsDemo class to limit the number of recursive calls. Here are the new codes.
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | package recursion; import java.util.Stack; public class TwoSiblingsDemo { private byte MIN_LEVEL_NOT_ALLOWED = 3; private final Stack<Integer> stack = new Stack<>(); public void recursion(TwoSiblingsBean root) { checkRecursionLimit(); System.out.println(root.getName()); if(root.getLeft() != null) { stack.push(0); recursion(root.getLeft()); } if(root.getRight() != null) { stack.push(0); recursion(root.getRight()); } if(!stack.isEmpty()) { stack.pop(); } } private void checkRecursionLimit() { if(stack.size() >= this.MIN_LEVEL_NOT_ALLOWED) { throw new RuntimeException( String.format("Maximum # of recursions reached. [ max=%s, current=%s]", this.MIN_LEVEL_NOT_ALLOWED, stack.size())); } } public static void main(String[] args) { // Root TwoSiblingsBean b1 = new TwoSiblingsBean("A"); // Children of root b1.setLeft(new TwoSiblingsBean("B")); b1.setRight(new TwoSiblingsBean("C")); b1.getLeft().setLeft(new TwoSiblingsBean("D")); b1.getLeft().getLeft().setLeft(new TwoSiblingsBean("D1")); b1.getLeft().getLeft().setRight(new TwoSiblingsBean("D2")); b1.getLeft().setRight(new TwoSiblingsBean("E")); b1.getLeft().getRight().setLeft(new TwoSiblingsBean("E1")); b1.getLeft().getRight().setRight(new TwoSiblingsBean("E2")); b1.getRight().setLeft(new TwoSiblingsBean("C1")); b1.getRight().setRight(new TwoSiblingsBean("C2")); TwoSiblingsDemo demo = new TwoSiblingsDemo(); demo.recursion(b1); } } |
[wp_ad_camp_5]
Outputs
1 2 3 4 5 6 7 8 9 10 | A B D Exception in thread "main" java.lang.RuntimeException: Maximum # of recursions reached. [ max=3, current=3] at recursion.TwoSiblingsDemo.checkRecursionLimit(TwoSiblingsDemo.java:43) at recursion.TwoSiblingsDemo.recursion(TwoSiblingsDemo.java:13) at recursion.TwoSiblingsDemo.recursion(TwoSiblingsDemo.java:19) at recursion.TwoSiblingsDemo.recursion(TwoSiblingsDemo.java:19) at recursion.TwoSiblingsDemo.recursion(TwoSiblingsDemo.java:19) at recursion.TwoSiblingsDemo.main(TwoSiblingsDemo.java:71) |
