Reverse a char array

[thisisdarshan]

How to reverse a char array with single traversal in place and in memory?
Hint: Use of recursion

[Sebastiani]

Hint: Do your own homework. Post code and specific questions if you get stuck.

[thisisdarshan]

My solution program:

void reverse_string(char str[])
{
    char c;
    char *p, *q;

    p = str;
    if (!p)
        return;

    q = p + 1;
    if (*q == '\0')
        return;

    c = *p;
    reverse_string(q);

    while (*q != '\0') {
        *p = *q;
        p++;
        q++;
    }
    *p = c;

    return;
}

I am looking for the best solution possible for the question. I was thinking the use of recursion and let compiler use the stack internally. This will also make solution in memory. Can anyone try this approach?

[iMalc]

If the char array is of a known length then you don't need recursion for it as it can be solved with a trivial loop over half the items performing swaps as you go. That would make the hint stupid, as you don't need (or bennefit from) recursion.

If however the length is unknown then I'm going to suggest that this technically isn't possible as you first traverse the array in one direction looking for the end, and then you perform a second traversal to perform the reversing. Whether there is recursion involved or not, it's still two passes, no matter how you look at it. You just cant call a pass over the array one direction then the other, a single traversal IMHO.

I therefore declare the question to be faulty.

[Adak]

I prefer using two pointers or indexes, and a single return line, when startIndex >= endIndex. With every recursion, the values of the array that startIndex and endIndex point to, (or reference), are swapped, and startIndex incremented Also, endIndex is decremented with every recursive call.

Then you are reversing the string, in one pass, and the code is crystal clear. Try that.

//before this function is called, startIndex and endIndex refer to the first and last char's
void reverseString(char *string, startIndex, endIndex) {
  //if the index variables have met or crossed, then return, here

  reverseString(string, startIndex+1, endIndex-1);
}

[quzah]

size_t rev( char s[], size_t x )
{
    if( s && s[x] )
    {
        size_t y = rev( s, x+1 );
        if( x < y / 2 )
        {
            char t = s[x];
            s[x] = s[y-1-x];
            s[y-1-x] = t;
        }
        x = y;
    }
    return x;
}
...
rev( myarray, 0 );

In place, one pass, unknown size.


Quzah.