# Recursive string reverse function

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

• 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. – Bobby Feb 20 '12 at 12:01
• That's right. Thank you. Should I delete my question since it isn't very useful? – cimere Feb 20 '12 at 13:20
• If you don't need it anymore now, then yes. If you still want a review, leave it here but edit it. – Bobby Feb 20 '12 at 14:03
• Probably not worth an answer but I don't think you really need to set 0 to i when i == 0. – SylvainD Feb 20 '12 at 14:44

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.

• Can you explain in more detail why it entirely misses the point? – cimere Feb 23 '12 at 8:57
• @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). – Anton Golov Feb 23 '12 at 15:51
• 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. – JeremyP Apr 23 '12 at 16:13

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.

• Helper function should be declared static. – 200_success Jan 7 '14 at 10:40
• I think, you meant to subtract 1 from end rather than adding. – Ammar Jan 23 '14 at 9:23

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.