Recursive Sort/Swap Conversion

[acerious]

Here I have some code that will run a program that generates a bunch of lowercase and uppercase letters from length 15-25 and will swap it first using an iterative swap method. It will then generate a second set of letters and will swap it this time with a recursive function.

How do I convert this iterative swap to a recursive swap guys? thanks.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

const int MAXSIZE = 25;

void ConstructArray (char [], int);
void printArray (const char [], int);
void iterativeSwap (char [], int);
void recursiveSwap (char [], int, int, int);
int main ()
{
    char myArray [MAXSIZE], myArrayR [MAXSIZE];

    static int left = 0;
    static int right;

    srand (time(NULL));

    int randomSize = rand() % 11 + 15;
    int randomSizeR = rand() % 11 + 15;

    right = randomSizeR - 1;

    ConstructArray (myArray, randomSize);
    printArray (myArray, randomSize);
    iterativeSwap (myArray, randomSize);
    ConstructArray (myArrayR, randomSizeR);
    printArray (myArrayR, randomSizeR);
    recursiveSwap(myArrayR, randomSizeR, left, right);
}

void ConstructArray (char myArray [], int randSize)
{
    char randUppcase, randLowcase;
    int randDuty;

    for (int i = 0; i < randSize; i++)
    {
        randDuty    = rand() % 2 + 1;
        randUppcase = rand() % 26 + 65;
        randLowcase = rand() % 26 + 97;

        if (randDuty == 1)
            randDuty = randUppcase;
        else
            randDuty = randLowcase;

        myArray [i] = randDuty;

    }




}


void printArray (const char myArray [], int randSize)
{
    cout << "Given the following array " << endl;
    for (int i = 0; i < randSize; i++)
        cout << myArray[i] << "\t";
    cout << endl;
}


void iterativeSwap (char myArray [], int randSize)
{
    int i = 0;
    int j = randSize - 1;

    while (i != j)
    {
        if (myArray[i] >= 'A' && myArray[i] <= 'Z')
        {
            if (myArray[j] >= 'a' && myArray[j] <= 'z')
            {
                swap(myArray[i],myArray[j]);

            }
            else
                --j;
        }
        else
            ++i;

    }

    cout << "Iterative Swap" << endl;
    for(int i = 0; i < randSize; i++)
        cout << myArray[i] << "\t";
    cout << endl;
}


void recursiveSwap(char myArrayR[], int randSizeR, int left, int right)
{

    if (left == right)


        return;

    else
        {
        recursiveSwap(&myArrayR[left], NULL, left +1, NULL);
        if (myArrayR[left] >= 'A' && myArrayR[left] <= 'Z')

            {
        recursiveSwap(&myArrayR[right], NULL, right -1, NULL);
        if (myArrayR[right] >= 'a' && myArrayR[right] <= 'z')
                swap (left, right);
            }

            }

    cout << "Recursive Swap" << endl;
    for(int i = 0; i < right; i++)
    cout << myArrayR[i] << "\t";
    cout << endl;
    return;

}

[mike_2000_17]

First, you should split the recursive function into two: the top-level function (that is called from main) and the function that is called recursively. You use the top-level function to make the initial call to the recursive function, and then report the result.

As so:

void recursiveSwap_impl(char myArrayR[], int left, int right)
{
    if (left == right)
        return;
    else
    {
        recursiveSwap_impl(&myArrayR[left], left + 1, right);
        if (myArrayR[left] >= 'A' && myArrayR[left] <= 'Z')
        {
            recursiveSwap_impl(&myArrayR[right], left, right - 1);
            if (myArrayR[right] >= 'a' && myArrayR[right] <= 'z')
                swap (myArrayR[left], myArrayR[right]);
        }
    }
    return;
}

void recursiveSwap(char myArrayR[], int randSize)
{

    recursiveSwap_impl(myArrayR, 0, randSize-1);

    cout << "Recursive Swap" << endl;
    for(int i = 0; i < randSize; i++)
    cout << myArrayR[i] << "\t";
    cout << endl;
    return;
}

That's the basic structure. I've fixed a few basic things in your recursive implementation, but the logic is wrong, and so is the logic of your iterative version too. Have you tried to run it? What your iterative version will do is find the first pair of letters and then it will loop infinitely by swapping the pair back and forth. To fix that, you need, at line 82, a statement of ++i; --j; to move the positions after the swap has been done. Also, the condition for looping should be while (i < j), because it is possible that i gets incremented while j gets decremented and they end up not being equal but that j is before i after you just cross the middle of the array. In other words, your iterative loop should look like this:

while (i < j)  // loop until i and j cross at the middle
{
    if (myArray[i] >= 'A' && myArray[i] <= 'Z')
    {
        if (myArray[j] >= 'a' && myArray[j] <= 'z')
        {
            swap(myArray[i],myArray[j]);
            ++i; --j;  // move on to the next (i,j) pair 
        }
        else
            --j;  // skip one character on 'j'
    }
    else
        ++i;  // skip one character on 'i'
}

Now, this is the logic that you should try to reproduce with your recursive function. Notice how each cases (if or else) within the loop ends up incrementing/decrementing one or both of the "left" and "right" indices, and then lets the loop immediately go back to the start (checking the while-condition, and then re-entering the loop). If you see the start of the loop as the start of the recursive function, the while-condition as an initial check at the start of the recursive function, and the increment-and-loop-again as a recursive call in order to repeat the process but with a different set of indices, then you have yourself a recursive function. That is literally how you turn an iterative function into a recursive one. I'll let you try to do that for yourself.