Java - Returning from a recursive function

Question

I'm trying to return all possible permutations of values in a String array. I've come up with the following code making all possible permutations; it works fine.

private void combineArray(String sPrefix, String[] sInput, int iLength) {
    if (iLength == sPrefix.length()) {
        //This value should be returned and concatenated:
        System.out.println(sPrefix);
    } else {
        for (int i=0; i<sInput.length; i++) {
            combineArray(sPrefix.concat(sInput[i]), ArrayUtils.removeElement(sInput, sInput[i]), iLength);
        }
    }
}

If I put in {x, y ,z} it prints to the console:

xyz
xzy
yxz
yzx
zxy
zyx

My problem is that I can't find a way to return these values to the original calling function. So I'd like this function not to return 'void' but a 'String' containing the concatened values of sPrefix.

I've been struggling with this for a while now and I can't seem to see clearly anymore. :) Any help would be appreciated.

Why not return a list with all the String combinations added? Even better, no? — thatidiotguy
– thatidiotguy, Commented Sep 27, 2012 at 19:58
Just throwing out ideas, but could you alter an outside array during each iteration, or return an array of values that would return through each recursive level? — Xiphos
– Xiphos, Commented Sep 27, 2012 at 20:01
Yeah, just return the data from the recursive routine. You can return either a regular [] array, or one of the collection classes, the latter being better as you can add to it as you return from each level. — Hot Licks
– Hot Licks, Commented Sep 27, 2012 at 20:04
LOL, you're all ridiculously fast. :) Thanks! I initially thought passing in a list parameter wouldn't work because Java only passes by value and not by reference, as far as I know... ? Also, is there no elegant way of using return statements? — Michiel Meulendijk
– Michiel Meulendijk, Commented Sep 27, 2012 at 20:12
Java passes all objects by reference. Only "scalers" -- ints, chars, floats, etc -- are passed by value. — Hot Licks
– Hot Licks, Commented Sep 28, 2012 at 2:32

ruakh · Accepted Answer · 2012-09-27 20:03:05Z

4

Rather than returning a list, I think it might work better to pass in a list as an argument, and populate it inside the method:

private void combineArray(List<String> lOut, String sPrefix, String[] sInput, int iLength) {
    if (iLength == sPrefix.length()) {
        //This value should be returned and concatenated:
        System.out.println(sPrefix);
        lOut.add(sPrefix);
    } else {
        for (int i=0; i<sInput.length; i++) {
            combineArray(lOut, sPrefix.concat(sInput[i]), ArrayUtils.removeElement(sInput, sInput[i]), iLength);
        }
    }
}

You can then have a wrapper method that creates the new ArrayList<String>, passes it into the above method, and returns it.

answered Sep 27, 2012 at 20:03

ruakh

185k29 gold badges292 silver badges324 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Rohit Jain · Accepted Answer · 2012-09-27 20:01:52Z

1

You can have an ArrayList<String> and add all the strings to it.. And then you can return this ArrayList..

List<String> listString = new ArrayList<>();
private void combineArray(String sPrefix, String[] sInput, int iLength) {
    if (iLength == sPrefix.length()) {
        listString.add(sPrefix);
        //This value should be returned and concatenated:
        System.out.println(sPrefix);
    } else {
        for (int i=0; i<sInput.length; i++) {
            combineArray(sPrefix.concat(sInput[i]), ArrayUtils.removeElement(sInput, sInput[i]), iLength);
        }
    }
    return listString;
}

answered Sep 27, 2012 at 20:01

Rohit Jain

214k45 gold badges419 silver badges534 bronze badges

Comments

srini.venigalla · Accepted Answer · 2012-09-27 20:03:32Z

-1

Keep appending to the same output.. Like this:

private String combineArray(String sPrefix, String[] sInput, int iLength, String output) {
    if (iLength == sPrefix.length()) {
        //This value should be returned and concatenated:
        System.out.println(sPrefix);
        output = output+"|+sPrefix;
        return output;
    } else {
        for (int i=0; i<sInput.length; i++) {
            output = combineArray(sPrefix.concat(sInput[i]), ArrayUtils.removeElement(sInput, sInput[i]), iLength, output);
        }
    }
}

You can also use a ListArray instead of a String, once the basic concept works..

answered Sep 27, 2012 at 20:03

srini.venigalla

5,1551 gold badge21 silver badges29 bronze badges

Collectives™ on Stack Overflow

Java - Returning from a recursive function

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related