Recursion with C

Question

I have the code below to reverse a string recursively, it works when I print the chars after the recursion is finished, but I can not figure out how to assemble the reverse chars into a string and return them reversed to the caller. Anyone have an idea? I don't want to add another parameter to accumulate chars, just this way, this is not homework, I am brushing up on small things since I will be graduating in a year and need to do well on interviews.

char* reversestring5(char* s)
{

    int i = 0;
    //Not at null terminator
    if(*s!=0)
    {

        //advance the pointer
        reversestring5(s+1);
        printf("%c\n",*s);
    }

}

Answer 1

With a recursive function, it's usually easiest to first figure out how to solve a trivial case (e.g. reversing a string with just a pair of characters) and then see how one might divide up the the problem into simple operations culminating with the trivial case. For example one might do this:

This is the actual recursive function:

char *revrecurse(char *front, char *back)
{
    if (front < back) {
        char temp = *front;
        *front = *back;
        *back = temp;
        revrecurse(front+1, back-1);
    }
    return front;
}

This part just uses the recursive function:

char *reverse(char *str)
{
    return revrecurse(str, &str[strlen(str)-1]);
}

Note that this assumes that the pointer is valid and that it points to a NUL-terminated string.

If you're going to actually reverse the characters, you can either provide a pair of pointers and recursively swap letters (which is what this routine does) or copy the characters one at a time into yet another space. That's essentially what your original code is doing; copying each character at a time to stdout which is a global structure that is not explicitly passed but is being used by your routine. The analog to that approach, but using pointers might look like this:

#define MAXSTRINGLEN 200

char revbuf[MAXSTRINGLEN];
char *refptr = revbuf;

char *revstring(char *s)
{
    if (*s != 0)
    {
        revstring(s+1);
        *refptr++ = *s;    /* copy non-NUL characters */
    } else {
        *refptr++ = '\0';  /* copy NUL character */
    }
    return revbuf;
}

In this minor modification to your original code, you can now see the reliance of this approach on global variables revbuf and refptr which were hidden inside stdout in your original code. Obviously this is not even close to optimized -- it's intended solely for explanatory purposes.