8
\$\begingroup\$

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

3 Answers 3

6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Can you explain in more detail why it entirely misses the point? \$\endgroup\$
    – cimere
    Feb 23, 2012 at 8:57
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ Feb 23, 2012 at 15:51
  • \$\begingroup\$ 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. \$\endgroup\$
    – JeremyP
    Apr 23, 2012 at 16:13
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Helper function should be declared static. \$\endgroup\$ Jan 7, 2014 at 10:40
  • 1
    \$\begingroup\$ I think, you meant to subtract 1 from end rather than adding. \$\endgroup\$
    – Ammar
    Jan 23, 2014 at 9:23
1
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.