CODEWITHSUNDEEP
c++stringrecursionpermutation
robotsatwar
robotsatwar

Reputation: 3

Iterative / Recursion

I have written the code for how to find the permutations for a given string using a for loop. I followed my professor's pseudocode, but am not sure how to convert it so that it is recursive. (no for, goto, while, STL algorithms).

void perms(string prefix, string rest)
{
    //  Followed Format of Pseudocode that Professor gave us
    //  If nothing remains in the rest string cout what we have for prefix
    if (rest == "")
    {
        cout << prefix << endl;
    }
    else
    {
        for (int i = 0; i < rest.length(); i++)
        {
            string prefix2 = prefix + rest[i];
            string rest2 = rest.substr(0, i) + rest.substr(i + 1);
            perms(prefix2, rest2);
        }
    }
}

The code works well, just need help with turning it to recursion.

Upvotes: 0

Views: 112

Answers (2)

Sylwester
Sylwester

Reputation: 48745

Every loop can be turned into recursion: 

void test() {
    int functionVar = 10;
    int sum = 0;
    for (int i=0, int j=2; i<10; i = i - 1, j = j + 2) {
       sum = sum + someFun(i, functionVar);
    }
    // Do something with sum
    cout << sum << endl;
}

Can easily be rewritten like this:

int forReplacement(int i, int j, int sum, functionVar) {
    if (i < 2) {
      return forReplacement(i - 1, j + 2, sum + someFun(i, functionVar), functionVar);
    }
    return sum;
}

void test() {
    int functionVar = 10;
    int sum = forReplacemenrt(0, 0, 0, functionVar);
    // Do something with sum
    cout << sum << endl;
}

You could make forReplacement a lambda and point reference it in it's closure to be able to recur and then functionVar and sum could be closure variables.

Upvotes: 0

Kaz
Kaz

Reputation: 58550

To hoist the loop into the recursion, you have to turn the iteration variable i into a parameter:

Step 1:

void printPermutations(string prefix, string rest, int i = 0)

Step 2:

void printPermutations(string prefix, string rest, int i = 0)
{
    //  Followed Format of Pseudocode that Professor gave us
    //  If nothing remains in the rest string cout what we have for prefix
    if (rest == "")
    {
        cout << prefix << endl;
    }
    else if (i < rest.length())
    {
       // original loop body
       string prefix2 = prefix + rest[i];
       string rest2 = rest.substr(0, i) + rest.substr(i + 1);

       // true original recursion with different prefix and tail.
       printPermutations(prefix2, rest2);

       // loop continuation via tail recursion: original prefix, next i.
       printPermutations(prefix, rest, i + 1);
    }
}

It's almost mechanical transformation. Firstly, the initialization of i to 0 has moved into the argument list where we do that via defaulting (we could also have callers explicitly pass zero, when necessary). The for loop header of the loop has been gutted, replaced just with the loop guard condition, which is transformed to an if conditional. And then the continuation of the loop is done just by a tail call where we pass i + 1, which becomes the next value of i.

It might help to imagine this intermediate version, which is still iterative:

void printPermutations(string prefix, string rest)
{
    int i = 0;

topOfFunction:

    //  Followed Format of Pseudocode that Professor gave us
    //  If nothing remains in the rest string cout what we have for prefix
    if (rest == "")
    {
        cout << prefix << endl;
    }
    else if (i < rest.length())
    {
       // original loop body
       string prefix2 = prefix + rest[i];
       string rest2 = rest.substr(0, i) + rest.substr(i + 1);

       // true original recursion with different prefix and tail.
       printPermutations(prefix2, rest2);

       // loop continuation via tail recursion: original prefix, next i.
       i = i + 1;
       goto topOfFunction;
    }
}

Note that though the rest == "" check is included in the loop, we know that stays false because we never modify rest.

Upvotes: 2

Related Questions