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\$
  • 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 '12 at 12:01
  • \$\begingroup\$ That's right. Thank you. Should I delete my question since it isn't very useful? \$\endgroup\$ – cimere Feb 20 '12 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 '12 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\$ – Josay Feb 20 '12 at 14:44
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\$
  • \$\begingroup\$ Can you explain in more detail why it entirely misses the point? \$\endgroup\$ – cimere Feb 23 '12 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\$ – Anton Golov Feb 23 '12 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 '12 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\$
  • \$\begingroup\$ Helper function should be declared static. \$\endgroup\$ – 200_success Jan 7 '14 at 10:40
  • \$\begingroup\$ I think, you meant to subtract 1 from end rather than adding. \$\endgroup\$ – Ammar Jan 23 '14 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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