1

I am looking at a permutation program written here. The code looks like this:

public static void main(String[] args) {
    permutation("", "CAT");
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1));
        }
    }
}

For the word CAT, I get the following output:
CAT
CTA
ACT
ATC
TCA
TAC

I can trace through the steps of the recursion and understand how it works to get CAT and CTA, but I don't see how it keeps going. After n == 0 (which is the base case) everything should stop (which would happen after we get CTA).

Other sources:
I read the explanation here, but I'm still having trouble understanding how it keeps going. I feel like I get the concept of recursion. I can use it blindly, but I want to understand HOW it is working here.

There is another version of permutation recursion here, but that is using backtracking, and I understand that one a bit better. It's this tail recursive one I don't understand.

Question:
Can someone please explain how the recursion is working so that we get past CTA in the example above? This isn't homework. I'm just looking into different programs and working through some skillbuilders.

Thanks!

Community
  • 1
  • 1
JustBlossom
  • 1,259
  • 3
  • 24
  • 53

3 Answers3

1

Let's look at what the first call generates:

("" + str.charAt(0), str.substring(0, 0) + str.substring(0 + 1))
p("C", "AT")

("" + str.charAt(1), str.substring(0,1) + str.substring(1 + 1))
p("A", "CT")

("" + str.charAt(2), str.substring(0, 2) + str.substring(2 + 1))
p("T", "CA")

Each call extracts each letter of str and adds it to the current prefix. The first call puts each letter of the original string as the start of a permutation. Then, for each such permutation, the algorithm extracts each letter of the remaining suffix and adds it to the accumulating prefix, so that all possibilities are explored:

C AT
    CA T
    CT A
        "CAT"
        "CTA"

A CT
    AC T
    AT C
        "ACT"
        "ATC"

T CA
    TC A
    TA C
         "TCA"
         "TAC"
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
0

Remember the state (values of each local variable and parameters) for each recursive call. Only a single call ends after CAT is returned, the others continue where they left off.

Think of each recursive call as a call to an entirely new function that just happens to do the same exact thing.

This is how your function will execute. It might help if you also wrote the values of each local variable (in your case it's just i and the parameters) as well. I just wrote what calls what.

p("", "CAT") -> p("C", "AT") -> p("CA", "T") -> p("CAT", "") -> CAT and return
                                             -> return
                             -> p("CT", "A") -> p("CTA", "") -> CTA and return
                                             -> return
                             -> return
             -> p("A", "CT") -> ...
IVlad
  • 43,099
  • 13
  • 111
  • 179
  • So, I'm not sure if this is the right way to explain it, but I'll try. I start with p (x,y) and start working towards a base case. As I'm working towards the base case, I'm "returning" another function. For each function p(x*,y*) it says, "I'm going to work myself all the way down to the base case." So, it starts at the top and works it's way all the way down to the base case, but in the process of doing so, it has a whole bunch of other variations of those functions stacked up. So, after it gets to the first function's base case, it goes to the next function and does the same thing. – JustBlossom Oct 03 '15 at 22:01
0

To understand recursion we must start with "factorial recursion"

Joe Oliver
  • 36
  • 3