Programming Challenge: Permutations

My question refers to the Programming Challenge section of the website wherein one of the challenges is about determining the Permutations of a string. That solution of that program has me pulling my hair. It is a recursive algorithm. For an input string "cat", once "cat" and "cta" have been printed out, the value of variable "place" turns out to be 3. At that instance, the function should terminate as the for loop does not support values equal or greater than 3. By some sort of miracle, however, the value of variable place is 1 (I put a cout statement inside the for loop). How in the world can "place" possibly be 1 after it has been 2. There is nothing that decrements place.

You didn't post the code in question, but consider this:

Code:

---

function foo( arg )
    if arg > 0
        foo arg -1
    output arg

---

You call the function with some value, and as long as your argument is greater than 0, it recursively calls itself. Then when it returns from that, it prints that value (or if the if fails, and it skips recursion). So:

Code:

---

foo 3
    foo 2
        foo 1
            foo 0
                prints 0
            prints 1
        prints 2
    prints 3

---

Quzah.

Code:

---

#include <iostream>
#include <string>

using namespace std;

string swtch(string topermute, int x, int y)
{
        string newstring = topermute;
        newstring[x] = newstring[y];
        newstring[y] = topermute[x]; //avoids temp variable
        return newstring;
}
void permute(string topermute, int place)
{
        if(place == topermute.length() - 1)
        {
                cout << topermute << endl;
        }
        for(int nextchar = place; nextchar < topermute.length(); nextchar++)
        {
                cout << place << endl; //how can place be 1 after being 2. it is never decremented.
                permute(swtch(topermute, place, nextchar), place+1);
        }
}

int main()
{
                string str = "cat";
        permute(str, 0);
}

---

Well maybe it's you are passing copies of place into the function, thus when you escape from one of the recursive calls then you are starting again with the place as its value was at that level, something like that, i not really looked into it.

If that were true, then the value of place should be zero (as that is what it initially started out with). The fact that it's 1 has baffled me.

Have you tried tracing the code? You may need to write down the state of the stack for the current function call in order to keep your sanity, unless you have a good memory.

Left column is the first call, second column is a recursive call. Each has it's own loop over it's own copy of the place variable...

Code:

---

0
    0
    1
    2 // Now it's a 2
1    // and now it's a 1
    0
    1
    2
2
    0
    1
    2

---

Does it make sense yet?

I ran in the debugger stepping through carefully, one problem i think you have is there is no clearly defined exit condition for the recursion, but in any case it works with the for loop, so: The recursion goes on until place reaches a value of 3, the for loop is then skipped, then you exit out to where the value of place was 2, i would then have expected to step back into the for loop but it is again skipped, and this i dont know why, but the net effect is that you exit back out of the recursion again to where place = 1, this is what you are seeing output, am checking again with the call stack