Recursive function that reverse the words in a string

The program below is just for fun.

Since the program asks for recursion, then in principle, recursion should be the sole iteration technique. Assuming that the requirement is to only implement a single function, and that string is '\0' terminated, the following program illustrates how this is possible.

Basically, the technique is to use the value of count control the mode of the reverse function. There are three modes: initial call, reverse each word, and reverse string.

A positive count signals the initial call, and count represents the length of the string. On initial call, the program follows the algorithm recipe of: first reverse the input string, then reverse each word in the input string.

A count value of zero causes the function to find the beginning and end of the first word in the string, reverse it, and recursively repeat the process beginning after the just reversed word.

A negative count causes the function to reverse the string assuming its length is -(count + 1). The off by one length is used to make sure the string reversal case does not run into the word reversal case. Thus, a -1 count represents an empty string.

void reverse (char *string, int count) {
    if (string == NULL || *string == '\0') return;
    // positive count := initial call
    if (count > 0) {
        reverse(string, -count-1); // reverse the whole string
        reverse(string, 0);        // reverse each word in whole string
        return;
    }
    // zero count := reverse each word in the string
    // skip over whitespace, then find end of word, reverse word, repeat
    if (count == 0) {
        char *p = string;
        int sl = strspn(p, " \t");
        int wl = strcspn(p + sl, " \t");
        reverse(p + sl, -wl-1);    // reverse the found word
        reverse(p + sl + wl, 0);   // reverse each word in rest of string
        return;
    }
    // negative count := reverse string of length -(count + 1)
    // reverse the string by swapping first and last, then shrink
    count = -(count + 1);          // fix-up count value
    if (count < 2) return;
    char t = string[0];
    string[0] = string[count-1];
    string[count-1] = t;
    reverse(++string, ---count);
}

Note the lack of looping structures within the function. All loops are accomplished with recursion or hidden by standard library functions strspn and strcspn.

When programming in general, C in particular, the most important quality is quite often program performance. As in execution speed and memory use. It is therefore very important to actually know what makes an efficient program and what makes an inefficient program. Inefficient == bad.

Some examples of inefficient programming:

• Iterating over the same data multiple times.
• Calling functions with the same or nearly the same data multiple times.
• Using recursion.

You should avoid all of these like the plague! Now, I know your specification says "use recursion". So what a professional would do first of all, is to question if the specification makes sense. In this case it doesn't - there is absolutely no need to use recursion here.

Others have given you diverse ways of solving this with recursion. Here is an alternative approach which is efficient, instead of needlessly inefficient.

#include <string.h>
#include <stdio.h>


void reverse_words (size_t str_length, 
                    char dest [static str_length+1], 
                    const char src [str_length+1])
{
  size_t word_length;
  const char* word_end = src + str_length;       // point 1 character past last word
  char* dest_ptr = dest;
  for(const char* src_ptr = word_end-1; src_ptr > src; src_ptr--)
  {
    if(*src_ptr == ' ')
    {
      word_length = (size_t)(word_end - src_ptr - 1);
      memcpy(dest_ptr, src_ptr+1, word_length);
      dest_ptr += word_length;

      *dest_ptr = ' ';
      dest_ptr++;

      word_end = src_ptr;
    }
  }

  // special case, last word
  word_length = (size_t)(word_end - src);
  memcpy(dest_ptr, src, word_length);
  dest[str_length] = '\0';
}

int main()
{
  const char str_cat [] = "cat is running";
  char str_reverse [sizeof(str_cat)];
  reverse_words(sizeof(str_cat)-1, str_reverse, str_cat);
  puts(str_reverse);

  const char str_one [] = "oneword";
  reverse_words(sizeof(str_one)-1, str_reverse, str_one);
  puts(str_reverse);

  return 0;
}

Explanation:

• The first thing you need to consider when designing this algorithm is if you need to reverse the string "in place" or make a reversed copy of it. The former might be more efficient, but the latter probably makes the most sense. It is usually good programming practice to treat strings as immutable.

  Depending on which method you pick, you end up with entirely different algorithms. I chose to make a copy of the original string.

• The function takes advantage of VLAs, so that you can give two arrays of any length as input. The arrays will of course decay into pointers to the first element. But it is often preferable to use array type in function parameters over pointer type: it gives self-documenting code and also better type safety if you use external static analysis tools to check your code.

• The static array length means that the dest parameter is guaranteed to be at least str_length+1 characters long. This makes the function slightly more flexible and ever so slightly faster (because the compiler can do a few more micro optimizations).

• The algorithm itself iterates over the source string from the end towards the beginning. This makes it easier to pick out the words in reverse order, without the need of temporary buffers. So there is one pointer to keep track of where we are in the destination string and one to keep track of where we are in the source string (used as loop iterator).

• The algorithm keep tracks of the end of the last found word. It is custom to design "end" pointers so that they point 1 past the end of the buffer. It could as well point at the last character in the last found word, for a slightly different algorithm. Doesn't matter.

• Whenever finding a space, the algorithm uses memcpy to effectively copy the whole word. Note that memcpy is much more efficient than byte-by-byte copy on most CPUs, since it can grab whole chunks of data at once.

• After copying, the algorithm manually inserts a space in the destination string.

• Reaching the beginning of the string is a special case: there won't be no space there, but when we reach the beginning there will always be a word to copy. So this is handled separately. This is also the reason why the loop iterates to src_ptr > src rather than src_ptr >= src. (As a side note, it is questionable/poorly-defined practice to point one past the beginning of an array in C, as opposed to pointing one past the end.)

• Finally, the new string has to be null terminated.

Unlike any code using recursion, this code is efficient. Feel free to benchmark against the recursion versions and note the vast improvement in speed and memory consumption.

( please note that naming a variable "str_cat" is very bad practice, I just couldn't resist sneaking in a C programming joke :) )