current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite

I have written a method for my homework to compute all of the permutations of a array of integer numbers with recursion. ( I am trying to implement backtracking algorithm). but it cause StackOverflowException for computing the premutaions of more than 7 numbers. I dont know how to solve this problem. does it still implement backtracking if I use itration?

code:

solve(0, arr, currentS);
//****************

private static void solve(int i, ArrayList<Integer> arr, int[] currentS) {
    if (i == arr.size()) {
        for (int j : currentS) {
            System.out.print(j + ",");
        }

        System.out.println();

        currentS[i-1] = 0;
        solve(i - 2, arr, currentS);

    } else {
        int x = nextValue(i, currentS, arr);
        if (x != -1&&travers.isCompatible(arr, currentS.clone())) {
            currentS[i] = x;
            solve(i + 1, arr, currentS);
        }
        else if((i != 0))
        {
            currentS[i] = 0;
            solve(i - 1, arr, currentS);
        }
    }
    return;
}

nextValue() is method that check not to have duplicate in the children of a node of tree, of not to have duplicate from root to each leave

exception:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.ArrayList.get(Unknown Source) ....
share|improve this question
    
Are you required to use recursion for your solution? –  Bernard Jan 11 '11 at 18:00
2  
The critical piece of data is further down in the stack trace. Edit your post and include the entire stack trace –  Jim Garrison Jan 11 '11 at 18:05
    
@Bernard: No it is not neccessary, but as I wanted to implement backtracking I did it with the recursion. –  Elton.fd Jan 12 '11 at 6:25

2 Answers 2

up vote 2 down vote

Not to disillusion you, but my solution for this question has 14 lines of code. Perhaps you should rethink your approach.

Hint: You don't really need a separate list to hold the current permutation, you can permute (and unpermute) the array directly. That means you won't need any code to detect duplicates in the list.

But your problem is probably more basic. Wikipedia writes:

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the factorial function can be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n(n − 1)!. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly-designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached.

(emphasis mine). I don't see any attempt to guarantee that i == arr.length will ever be reached. Sometimes i gets smaller when recursing, sometimes it gets larger, it's quite possible that it'll simply oscillate without ever reaching the base case. Put differently, your program would never terminate, but since each recursion step needs additional memory, you run out of stack space.

share|improve this answer
up vote 0 down vote

Assuming that your algorithm is sound and works correctly for 7 numbers ...

Then what you may need is more stack space. This can be done on the Java command line by adding "-Xss1024k" for a 1 meg stack size. You can increase that more for more space. Doing so may give you what you need.

However, you must understand, there is ALWAYS an upper bound for stack space and a recursive algorithm will risk hitting that upper bound. You may be better off using a different algorithm that doesn't use the call stack to store the work you need to do. Sometimes it's better to use the heap space instead with something like an instance of a Queue or Stack class to hold your state.

share|improve this answer
    
Yes, there always is an upper bound, but any decent algorithm for this problem will require stack space linear in the length of the array, but exponential execution time (since the output has exponential size). Put differently, if you supply an input where a proper algoritms will hit the stack size limit, the universe will end before the algorithm terminates. –  meriton Jan 11 '11 at 18:42
    
@meriton - ignoring this specific example, I'd rather allocate 10MB for an instance of a Queue or Stack, then have to store an equivalent number of call stack frames, each of which would be larger than the corresponding entry in the collection. Recursion is elegant and often an interesting homework problem, but rarely the best solution in my opinion. –  rfeak Jan 11 '11 at 18:54
    
Obviously, recursion is not suitable for all problems. But it is suitable, and even best by any criteria I can imagine, here. –  meriton Jan 11 '11 at 19:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.