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
– Ingo, Commented Apr 10, 2011 at 20:56
Possible duplicate: stackoverflow.com/questions/717725/understanding-recursion (it may help you to read that first) — z7sg Ѫ
– z7sg Ѫ, Commented Apr 10, 2011 at 21:00
@z7sg : No i'm good in recursion i only want to make sure am thinking right — SuperMan
– SuperMan, Commented Apr 10, 2011 at 21:04
to remind an old joke: to understand recursion you must first understand recursion :) — Bozho
– Bozho, Commented Apr 10, 2011 at 21:05
@SuperMan OK I misunderstood. Perhaps this question will help: stackoverflow.com/questions/5614665/… — z7sg Ѫ
– z7sg Ѫ, Commented Apr 10, 2011 at 21:12

Roland Illig · Accepted Answer · 2011-04-10 21:16:47Z

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, 2011 at 21:16

Roland Illig

41.9k12 gold badges91 silver badges127 bronze badges

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

3 Comments

Roland Illig Over a year ago

That's weird. Any details on the error message? I tested it with Sun JDK 1.6.0_20, and it worked.

SuperMan Over a year ago

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.<init>(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)

Roland Illig Over a year ago

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.

ninjalj · Accepted Answer · 2011-04-10 21:08:50Z

1

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);

answered Apr 10, 2011 at 21:08

ninjalj

44.1k11 gold badges112 silver badges151 bronze badges

2 Comments

SuperMan Over a year ago

Yes i was doing this way. So i come back to increment i for the initial input right ?

ninjalj Over a year ago

@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.

Alex · Accepted Answer · 2011-04-10 21:16:22Z

1

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 ;)

answered Apr 10, 2011 at 21:16

Alex

4,9338 gold badges46 silver badges61 bronze badges

Collectives™ on Stack Overflow

Problem in Understanding Recursion - Java

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related