What is the cause of this stack overflow?

Question

I am writing a function in Java for an Android application that uses a StringBuilder to generate all permutations of a string.

Whenever the function is run, the program instantly terminates, and the DDMS (Dalvic Virtual Machine debugging tool) claims a stack overflow within my function.

private void reorder(String reorder_this, StringBuilder in_this){

    for(int i = 0; i < reorder_this.length(); i++)
    {
        if(i == reorder_this.length())
        {
            in_this.append(System.getProperty("line.separator"));
        }
        else
        {
            in_this.append(reorder_this.charAt(i));
            reorder(reorder_this.substring(0, i) + reorder_this.substring(i), in_this);
        }
    }
}

You can see that I have taken a recursive approach to this problem, which I believe will end up filling the string builder with all possible permutations of the inputted string each followed by the newline character.

Does anybody have an idea about what could be causing the stack overflow?

Answer 1

In short, your function cannot terminate unless your string has a length of 0.

Your method begins with setting i to 0 and testing whether i is less than length of your first argument. If it is (which will be the case for all but empty strings), you immediately recurse because you can not be strictly less than the length and equal to the length. In your recursive call, you pass in a string of exactly the same length (indeed, the same exact string, as Thilo points out). This indicates a second problem with the algorithm: recursive algorithms should operate on "smaller" arguments for each recursive call.

It will not take long to get a StackOverflowException here. Each recursive call pushes a new stack frame.