How does recursion work in a permutation?

Question

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!

Answer 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"

Answer 2

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") -> ...

Answer 3

To understand recursion we must start with "factorial recursion"