3
\$\begingroup\$

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?

\$\endgroup\$

4 Answers 4

2
\$\begingroup\$

@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".

\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$
    – syntagma
    Nov 22, 2014 at 15:52
  • \$\begingroup\$ 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 \$\endgroup\$
    – janos
    Nov 22, 2014 at 16:20
2
\$\begingroup\$
  • 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);
    }
    
\$\endgroup\$
2
  • \$\begingroup\$ I think you meant left > right. \$\endgroup\$
    – syntagma
    Nov 21, 2014 at 18:31
  • \$\begingroup\$ @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. \$\endgroup\$
    – vnp
    Nov 21, 2014 at 19:06
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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? \$\endgroup\$
    – syntagma
    Nov 22, 2014 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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