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 3 down vote favorite

This is function for reversing a string in C using recursive calls:

#include <stdio.h>
#include <string.h>

void revert(char* left, char* right) { // Should I pass char* like I'm doing now or are char** a better idea?
    if(left == right) return;

    char *ll = left; char* rr = right;

    char tmp = right[0];
    right[0] = left[0];
    left[0] = tmp;
    revert(++ll,--rr);
}

int main() {
    char rev_string[] = "Some teststring";
    printf("%s\n", rev_string);
    revert(&rev_string[0],&rev_string[strlen(rev_string)-1]);//rev_string[strlen(rev_string)-1]);
    printf("%s\n", rev_string); 
    return 0;
}

Can it be simplified? Can anything be written better?

share|improve this question

4 Answers 4

up vote 1 down vote accepted

@vnp is absolutely right on all counts. In addition, since the updated values of ++left and --right are not needed, I would prefer to use left + 1 and right - 1.

It's inconvenient and error prone for callers to set the end pointer. I recommend a wrapper function that takes a single char* parameter, and sets the end pointer correctly, for example:

void revert_recursive(char* left, char* right) {
    if (left < right) {
        char tmp = *right;
        *right = *left;
        *left = tmp;
        revert_recursive(left + 1, right - 1);
    }
}

void revert(char* str) { 
    revert_recursive(str, str + strlen(str) - 1);
}

To make the program easier to play around with, I recommend to make the main function work with command line arguments:

int main(int argc, char ** argv) {
    int i;
    char* arg;
    for (i = 1; i < argc; ++i) {
        arg = argv[i];
        printf("%s\n", arg);
        revert(arg);
        printf("%s\n", arg);
    }
    return 0;
}

Finally, in the question you described the task as reversing a string, but called the method "revert" instead of "reverse". The latter would be better, as "reverting" means more like "undoing".

share|improve this answer
    
Thanks, but why exactly is left + 1 and right - 1 better than ++left and --right? Wouldn't there be new values created in both cases? –  REACHUS Nov 22 at 15:52
    
In this particular example both yield the same result. But strictly speaking there's no need to modify the values of these local variables, so why do it then. Every operation in a program is a potential bug. So if an operation is unnecessary, then it's effectively a net negative, so it makes sense to not do it. Although the difference here may seem negligible, this is a matter of principle, neglecting it can lead to bad habits that are hard to cure –  janos Nov 22 at 16:20
up vote 2 down vote

  • There is a bug. Some teststring contains an odd number of characters, therefore a left == right condition is eventually hit. For an even-length string, it would never be satisfied. You should test for left < right instead.

  • There is absolutely no need to reassign left, right to ll, rr. revert(++left, --right) works as good.

    To clear the possible confusion (see comments) this is what I meant:

    if (left < right) {
    swap_values(left, right);
    revert(++left, --right);
}
share|improve this answer
    
I think you meant left > right. –  REACHUS Nov 21 at 18:31
    
@REACHUS Almost. I was automatically thinking for a positive case (if (condition) { do_stuff(); }). For a negative case, you need to test for left >= right. –  vnp Nov 21 at 19:06
up vote 1 down vote

I think you could simplify by using a length instead of right. Like this:

#include <stdio.h>
#include <string.h>

void reverse(char *s, size_t len) {
    if (len <= 1) return;

    char tmp = s[len-1];
    s[len-1] = s[0];
    s[0]     = tmp;
    reverse(s+1, len-2);
}

int main() {
    char rev_string[] = "Some teststring";
    printf("%s\n", rev_string);
    reverse(rev_string, strlen(rev_string));
    printf("%s\n", rev_string); 
    return 0;
}
share|improve this answer
up vote 1 down vote

The solution uses tail-recursion. Some compilers can optimize this into a simple jump. Others will create a full function call in every case. That quickly causes a stack overflow and limits the length of strings you can reverse.

It would be better to use a while or for loop instead of recursion.

share|improve this answer
    
I know that iterative approach would be better, I was just doing it as an exercise with pointers and recursion. Do you know how can I see how did a specific compiler optimize my code? –  REACHUS Nov 22 at 18:16

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.