String pattern search algorithm stack overflow

Question

I'm trying to modify this code to be a recursive version in order to have executing time efficiency. What the code does is to find all pattern's first indices in Text and add them to an ArrayList. My code is as below:

public boolean search(String text, int n, String pattern, int d) {
    if (n > text.length() || n < d) return true;
    while (d >= 0 && d < pattern.length() && n < text.length() && text.charAt(n) != pattern.charAt(d)) d = next[d];
    if (d == pattern.length()) {
    (***) if (ans == null || !ans.contains(n-d)) ans.add(n-d);                    
          n = n-d;
          d = -1;
    }
    if( n < text.length() && n >= d ) search(text, n+1, pattern, d+1);
    return false;
}

For-loop version of my code:

public void search(String text) {
int m = this.pattern.length();
int n = text.length();
int i, j;
for (i = 0, j = 0; i < n && j < m; i++) {
    while (j >= 0 && text.charAt(i) != this.pattern.charAt(j)) {
        j = next[j];
    }
    j++;
    if (j >= m) {
    if (ans == null || !ans.contains(i-m+1) ) ans.add(i-m+1);     
        j = 0;
        i = i - m + 1;
    }
}}

For worse case, it's exponential, that's why I'm unable to meet time limit.

Array next[] is the same as example code. My questions are:

1. When argument Text string is getting bigger, say more than 2200 characters, it always raised an java.lang.StackOverflowError; specifically in the line of three asterisks inside parenthesis. Even if only ans.add(n-d) left, still the same problem. Return value boolean is meanless, even if I changed function return type to be void and remove last line, it's still the same problem.

2. Is there any better way to do this?

Answer 1

Currently the JVM (Hotspot) does not have tail call optimization. So each recursion will consume stack. So you get stackoverflow error. It's better to stick to iterative approach at the moment.