Problem in Understanding Recursion - Java

Question

I got the code from this question, I ran it in Eclipse and the code was fine, but I confused myself in how the recursion order goes internally.

public class Permute {
    public static void main(String[] args) throws IOException {
        System.out.println("Enter a string");
        BufferedReader bufReader = new BufferedReader(new InputStreamReader(
                System.in));
        String text = bufReader.readLine();
        shuffle("", text);
    }

    public static void shuffle(String dummy, String input) {
        if (input.length() <= 1)
            System.out.println(dummy + input);
        else {
            for (int i = 0; i < input.length(); i++) {
                input = input.substring(i, i + 1) + input.substring(0, i)
                        + input.substring(i + 1);
                shuffle(dummy + input.substring(0, 1), input.substring(1));

            }
        }
    }
}

I found difficulty in understanding recursion in the for loop of Shuffle. Any pointers in decoding the recursion steps?

EDIT : Okay this is my understanding, say suppose my input is ABC and when i run in the first loop , i get dummy = A and input = BC, so the immediate step would be to go down the recursion for input = BC and dummy = A and then come back to iterate i for the initial input ?

Trace the calls to shuffle along with actual arguments, and you will underatand. — Ingo, Apr 10 '11 at 20:56
Possible duplicate: http://stackoverflow.com/questions/717725/understanding-recursion (it may help you to read that first) — z7sg Ѫ, Apr 10 '11 at 21:00
@z7sg : No i'm good in recursion i only want to make sure am thinking right — SuperMan, Apr 10 '11 at 21:04
to remind an old joke: to understand recursion you must first understand recursion :) — Bozho, Apr 10 '11 at 21:05
@SuperMan OK I misunderstood. Perhaps this question will help: http://stackoverflow.com/questions/5614665/problem-in-understanding-recursion-java — z7sg Ѫ, Apr 10 '11 at 21:12

score 1 · Answer 1 · answered Apr 10 '11 at 21:08

Think of it as dividing the job in steps. Your shuffle function takes two arguments, dummy for the part of the string that is already shuffled, and input for the part of the string that still has to be shuffled.

At every step, you shuffle the first character of input:

        for (int i = 0; i < input.length(); i++) {
            input = input.substring(i, i + 1) + input.substring(0, i)
                    + input.substring(i + 1);

and then, recursively apply the algorhythm, with the part already shuffled being a character longer:

            shuffle(dummy + input.substring(0, 1), input.substring(1));

Until there is nothing more to shuffle:

    if (input.length() <= 1)
        System.out.println(dummy + input);

Yes i was doing this way. So i come back to increment i for the initial input right ? — SuperMan, Apr 10 '11 at 21:10
@SuperMan: think of the recursive call as a black box that does the algorhythm on an input of length - 1. It's similar to thinking of mathemathical induction, if you know about that. — ninjalj, Apr 10 '11 at 21:14

score 1 · Answer 2 · answered Apr 10 '11 at 21:16

It exhaustively shuffles the input by the inputs length, recursively. So once each recursion has shuffled the string by the i'th term, it returns.

This would be an n-squared complexity algorithm in big-O notation.

The shuffling is tricky to work out without a debugger ;)

score 1 · Accepted Answer · answered Apr 10 '11 at 21:16

1

Add a global counter:

static int depth = 0; /* calling depth of the recursive method */

Add as the first line of shuffle:

System.out.printf("%" + depth++ + "s call dummy='%s' input='%s'\n", "", dummy, input);

Add as the last line of shuffle:

System.out.printf("%" + --depth + "s return\n", "");

Run the program. Now you can see what happens.

answered Apr 10 '11 at 21:16

Roland Illig

40,703
10
88
121

That's weird. Any details on the error message? I tested it with Sun JDK 1.6.0_20, and it worked. – Roland Illig Apr 10 '11 at 22:24
Exception in thread "main" java.util.FormatFlagsConversionMismatchException: Conversion = s, Flags = 0 at java.util.Formatter$FormatSpecifier.failMismatch(Unknown Source) at java.util.Formatter$FormatSpecifier.checkBadFlags(Unknown Source) at java.util.Formatter$FormatSpecifier.checkGeneral(Unknown Source) at java.util.Formatter$FormatSpecifier.(Unknown Source) at java.util.Formatter.parse(Unknown Source) at java.util.Formatter.format(Unknown Source) at java.io.PrintStream.format(Unknown Source) at java.io.PrintStream.printf(Unknown Source) – SuperMan Apr 10 '11 at 22:25
Ah, ok, I only tested the code with depth==13. so just initialize depth to 1, and it should work. The zero has a special meaning in this context, any other number will be fine. – Roland Illig Apr 10 '11 at 22:29

Problem in Understanding Recursion - Java

3 Answers3