string reversal recursively

Question

Ok, i wrote 2 versions of this program. But im looking for the best solution - the most simple and fast one.

This is my solution but i was told that this solution is O(n*n) slower, which i dont know what really means. I was also told i could fasten it by breaking it into 2 functions, could anyone help me doing this?

void reverse3(char s[])
{
     int l;
     int i;

     l = strlen(s);
     if(l > 1)
     {
          reverse3(s + 1);

          for(i = 1; i < l; i++)
          {
              int temp = s[i-1];
              s[i-1] = s[i];
              s[i] = temp;
          }
     }
}

Answer 1

You could certainly do much better swapping the element on one end with the element on the other end, and advance to the next element. You would then need two parameters: the pointer to the current element and the distance to the other end. The base case is the one with the distance <= 2. That would make your algorithm work in linear time (O(n))

Answer 2

You should swap the outermost bytes, i.e., i=1 and j=(l-1), then i=2, j=(l-2), etc. until i <= (j-1) (in other words, until either i=j, for an even number of characters, or i=j-1, for an odd number).

That will perform in O(n).

Recursion isn't necessary, and "breaking it into two functions" doesn't seem necessary either IMHO.

Ok, read your edit about this being part of the assignment.

In this case, you do need two functions to, as Jimmy said, preserve the parameter list of your "main" function.

The second function would be something like:

void swapRecursive(char[s], i, l) {      
   if(i >= (l-1) { return; } // no more swapping needed
   char t = s[i];
   s[i] = (l-i);
   s[l-i] = t;
   swapRecurse(s, i+1, l);
   }

Please excuse my rusty C, I live in C#, VB.NET, and JavaScript now, some of the details escape me.

Also, I may or may not have left a bug in there, since this is homework. ;)

Answer 3

I have to do it recursively, thats the part of the exercise:

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

So, i was told that this, my version, can be done faster.

I know how to write the non-recursive version.

Answer 4

You could certainly do much better swapping the element on one end with the element on the other end, and advance to the next element. You would then need two parameters: the pointer to the current element and the distance to the other end

for(i = 0, j = strlen(s) - 1; i < j; i++, j--) temp = s[i], s[i] = s[j], s[j] = temp;

Dont even need pointers actually.

Answer 5

Let's say your code does F(n) operations for an n-length string. Then, from the recursion you wrote we can see that:

F(2) = 2

F(n) = n + F(n-1) + (n-1)*5 = F(n-1) + 6n - 5

The first 'n' is the strlen, The F(n-1) is the recursive call, and the (n-1)*5 is from the for-loop (the 3 operations, and the "i< l", "i++").

If we open the formula we get:

F(n) = 6n-5 + 6(n-1)-5 + 6(n-2)-5 + ... + 6*(2)-5 = 6(2+3+4+...+n) - 5*n = 6(n(n+1)/2 -1) - 5n

F(n) = 3n^2 +3n -6 -5n = 3n^2 -2n -6

The last formula is obviously O(n^2).

You don't need recursion to reverse a text. Simple switch every i-char with the (l-i)-char.

void switch_chars(char *a, char *b) {
  char temp = *a;
  *a = *b;
  *b = temp;
}
void reverse(char s[]) {
  int l = strlen(s);
  for (int i=0; i<l/2; i++) {
    switch_chars(&s[i], &s[l-1-i]);
  }
}

Answer 6

void swapRecursive(char s[], int i, int len) {      

   if(i >= len/2+1) 
       return;

   char t = s[i];
   s[i] = s[len-i];
   s[len-i] = t;

   swapRecursive(s, i+1, len);
}

void reverse3(char s[])
{
     int i = 0;

     swapRecursive(s, i, strlen(s) - 1);
}

Thanks Richard, that was helpful!

Is this what you had in mind?

Answer 7

Actually splitting the problem into functions (and inline functions) might be a good idea.

The algorithm is quite simple, given a string of n characters, you swap the first character with the last character, the second with the last but one and so on until you've swapped every character.

This could be expressed like this in pseudocode:

str: string of length n
i <- 0
j <- n - 1

reverse (i, j):
   if i < j:
       swap str[i] and str[j]
       increment i
       decrement j
       reverse(i, j)

And this is a possible C implementation with pointers:

static inline void swapCharacters (char* a, char* b)
{
    *a += *b;
    *b = *a - *b;
    *a -= *b;
}

static void recursiveReverse (char* left, char* right)
{
    if (left < right) {
        swapCharacters(left, right);
        recursiveReverse(++left, --right);
    }
}

void reverseString (char* string)
{
    char* last = strchr(string, '\0') - 1; // Finds the first character before the terminator
    recursiveReverse(string, last);
}

Anyway this won't work if your string is a read-only buffer, for example if you try to do

char* string = "My string";
reverseString(string);

It will give you a segmentation fault.

So the best solution is actually to dynamically-allocate a buffer in which the reversed string is copied, then the buffer is returned and freed when it's no longer needed.