A recursive function to reverse string

Question

Write a recursive version of the function reverse(s), which reverses the string s in place.

I'm studying K&R and wrote a code for the question.

void reverse(char s[], int n)   // The seconde argument should be always 1.
{               // The function should be always called as reverse(s, 1);
    int temp;
    int len;

    len = strlen(s);
    if ((len + 1) / 2 > n)
        reverse(s, n + 1);
    
    temp = s[n-1];
    s[n-1] = s[(len - 1) - (n-1)];
    s[(len - 1) - (n-1)] = temp;
}

The second argument n says reverse() is currently called at n-th times. The function works as if it sets an axis of symmetry at s[(strlen(s) + 1) / 2](since integer division is truncated, it's not always symmetric by the axis but the function behaves as if truncation doesn't happen and it is exactly an symmetric axis) and accordingly change s[n - 1] with s[(strlen(s) - 1) - (n - 1)] and vice versa. The function stops its recursive call when the index of the axis is larger than n.

I saw other solutions(this and this). I think they used nice idea for the question. But I wonder how you think about mine. Thanks for reading!

Answer 1

To be honest, this is a bad way to solve the problem - recursion with strlen() is not a good idea. There was a recent discovery that Rockstar Games had their loading screens in GTA5 extended by several minutes due to their JSON parser calling strlen() on a string repeatedly.

Instead, when handling strings in a recursive manner that requires knowledge of the length of the string, one should pass that length alongside the pointer.

On the topic of length, you're storing the length of the string in a variable with type int rather than the size_t that strlen() returns. There are two problems with this - the first is that int is signed and size_t is unsigned, and the second is that size_t is often larger than int, especially with modern 64-bit systems defining the former as uint64_t and the latter as int32_t.

Lastly, you could avoid a lot of mental overhead by using two pointers instead - one to the beginning of the string, and one to the end of the string. You would then stop the recursion when the beginning is no longer before the end.

Answer 2

Bug: short string

Consider reverse("", 1). Code attempts s[-1] which leads to undefined behavior (UB).

len = 0;
s[(len - 1) - (1-1)]  // UB

Bug: long string

Pedantic: Code fails for huge strings longer than INT_MAX. Use size_t, not int.

Alternative

// left points to left-most character
// right points to right-most + 1 character
static void rev(unsigned char *left, unsigned char *right) {
  if (left < right) {
    unsigned char temp = *--right;
    *right = *left;
    *left = temp;  
    rev(left + 1, right);
  }
}
          
void reverse(char s[], int n)  {
  rev(s, s + strlen(s));
}