current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 8 down vote favorite
2

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;
}
share|improve this question
1  
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
    
Edited, thanks again. –  cimere Feb 20 '12 at 14:08
5  
Probably not worth an answer but I don't think you really need to set 0 to i when i == 0. –  Josay Feb 20 '12 at 14:44

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
Can you explain in more detail why it entirely misses the point? –  cimere Feb 23 '12 at 8:57
1  
@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
up vote 3 down vote

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.

share|improve this answer
    
Helper function should be declared static. –  200_success♦ Jan 7 at 10:40
    
I think, you meant to subtract 1 from end rather than adding. –  Ammar Jan 23 at 9:23
    
You are, of course, correct. Thanks –  Useless Jan 23 at 18:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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