Please criticize my recursive code

Question

I'm going ahead studying C on K&R and now I'm facing a recursion exercise that states: Write a recursive version of the function reverse(s), which reverses the string s in place. I've written the code below and I'm pretty sure that it works but I'll be glad to receive some critics about it.

Reverse function:

/* reverse: reverse string s in place */
void reverse(char s[])
{
    static int i, j = 0;
    int c;

    if (i == 0) {
        i = 0;
        j = strlen(s)-1;
    }
    c = s[i];
    s[i] = s[j];
    s[j] = c;
    i++;
    j--;
    while(i < j)
        reverse(s);
}

Here is the main:

#include <stdio.h>
#include <string.h>

#define MAXLINE 100

void reverse(char s[]);

int main(void)
{
    char s[MAXLINE] = "foo bar baz";

    reverse(s);
    printf("%s\n", s);
    return 0;
}

Answer 1

While this is recursive, it entirely misses the point. As the while loop will only ever execute once (because the function it calls only returns when i < j it could just as well have been an if, and thus all you've got is tail-recursion.

What you have is equivalent to the following, but impossible to call twice and maybe less efficient:

void reverse(char s[])
{
    int i = 0, j = strlen(s)-1;
    int c;
    while (i < j) {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
        i++;
        j--;
    }
}

That's obviously not recursive. The way you'd do it recursively is always swap the outer two characters of the string and then pass pointers to the beginning and end of a substring along.

Apart from that, you're initialising j but not i, which makes little sense: both will be 0 initially anyway, so at least be consistent. You're also not using MAXLINE, so you might as well get rid of it (if C allows it). You're also not checking for a NULL being passed in.

Answer 2

The usual recursive formulation for a task like this would be:

if (we're not at the end)
    save the first character
    reverse string starting from second character
    append the (previously) first character to the end of the reversed string

We probably don't, however, want to traverse the string to find the end every time. Instead, we probably want to figure out exactly where each character will go, and put it there. I'd probably do it something like this:

size_t rev(char *s) { 
    if (!*s)
        return 0;
    char a = *s;
    size_t pos = rev(s+1);
    s[pos] = a;
    return pos+1;
}

Answer 3

Simple worked example of Anton's suggestion:

void reverse_rec(char *begin, char *end)
{
    if (begin < end) {
        char swp = *begin;
        *begin = *end;
        *end = swp;
        reverse_rec(begin+1, end+1);
    }
}

void reverse(char s[])
{
    if (s)
        reverse_rec(s, s+strlen(s)-1);
}

Note that you don't need a while, because recurse_rec stops recursing when begin >= end.