Recursive reverse function

Question

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

Here is my solution:

void reverse(char a[], int i, int j) {
    char tmp;

    if(i >= j) {
        return;
    }

    reverse(a, i + 1, j - 1);
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

This exercise is right after the presentation of the quicksort algorithm.

This is the signature of the quicksort function presented in the book:

void qsort(int v[], int left, int right)

This is why I added 2 new parameters to the functions - to narrow the size of the array.

There are 2 base cases:

1. When i == j, so n is even
2. When i > j, so n is odd

n represents the number of characters in string s.

Answer 1

It looks ok to me.

As a few comments in a random order:

• I guess I don't have to tell you that writing a non-recursive function for this is quite straightforward.
• You could give tmp its final value as you define it : char tmp = a[i];.
• You could make it a tail call recursion by doing reverse(a, i+1, j-1) at the end.
• It might be a good option to define a function reverse taking only the array and the length as an argument and calling the one you've just posted here. If you were to use this function in a C++ program, you could do this with a single function definition if you use default parameter (i is 0 by default). The main drawback is that you have to give the parameter a somewhat awkward order.

Answer 2

Just to add my 2 cents on top of the comments of @Josay: in C you can make your function an helper function to a wrapper with a more convenient interface.

For instance you can think of passing only the \0 terminated string to the interface:

static void reverse_helper(char * str, size_t ii, size_t jj) {
  // Exchange characters
  char tmp = str[ii];
  str[ii]  = str[jj];
  str[jj]  = tmp;
  // Check next move
  ii++;
  jj--;
  if( ii >= jj) {
    return;
  }
  reverse_helper(str,ii,jj);
}

// Requires a '\0' terminated string
void reverse(char * str) {
    size_t str_length = 0;
    while( str[str_length] != '\0') {
        str_length++;
    }
    if (str_length == 0) return;
    reverse_helper(str,0,str_length-1);
}

Apart from this minor detail, your function looks completely fine to me.