Reversing a string in place without using iteration in C

Question

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?

Answer 1

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

• syntagma: 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?
• janos: 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

Answer 2

• 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);
  }
  

• syntagma: I think you meant left > right.
• vnp: @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.

Answer 3

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;
}

Answer 4

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.

• syntagma: 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?