5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ C functions can't have default parameters as in C++. You could have variadic functions, but that would be nasty. \$\endgroup\$ Jan 24 '14 at 7:47
  • \$\begingroup\$ Indeed, updated my answer. \$\endgroup\$
    – SylvainD
    Jan 24 '14 at 9:24
2
\$\begingroup\$

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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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