Recursive string reverse function

Question

I'm 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. I'll be glad to receive some critiques 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);
}

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;
}

• Bobby: What do you mean, you can't find a similar solution? The solution on that page from David Kachlon is pretty much the same, except that he does not use static variables and no while-loop.
• cimere: That's right. Thank you. Should I delete my question since it isn't very useful?
• Bobby: If you don't need it anymore now, then yes. If you still want a review, leave it here but edit it.
• SylvainD: Probably not worth an answer but I don't think you really need to set 0 to i when i == 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.

• cimere: Can you explain in more detail why it entirely misses the point?
• Komi Golov: @cimere: Because it doesn't function recurvively. The call you have could be replaced with a goto and nothing would change. By the way, Jerry's suggestion is better than mine (mine is also tail-recursion).
• JeremyP: I disagree, the function as written is properly recursive. Incidentally, it is not tail recursive because the recursive call is in a while statement. He shouldn't have used a while instead of an if and he should have used arguments instead of static variables (the if (i == 0) bug makes it a one shot function), but that doesn't make the function non recursive.

Answer 2

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.

• 200_success: Helper function should be declared static.
• Ammar: I think, you meant to subtract 1 from end rather than adding.

Answer 3

This doesn't work if you call reverse () more than once in one run of program:

char s[MAXLINE] = "foo bar baz";
reverse(s);
printf("%s\n", s); // get "zab rab oof"
reverse(s);
printf("%s\n", s); // get "zab rab oof"

This happens because of your use of static variables in function.