CODEWITHSUNDEEP
cstring
Tool
Tool

Reputation: 12488

String reversal recursively

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;
          }
     }
}

Upvotes: 2

Views: 1365

Answers (6)

Simon Peverett
Simon Peverett

Reputation: 4207

Thinking outside the box.

#include <stdio.h>
#define REVERSE(STRING) r(*(STRING),(STRING),(STRING)+1)

char *r(char v, char *s, char *n) {
    if (*n && *s) s = r(*n, s, n+1);
    *s = v;
    return s+1;
}

int main(int argc, char *argv[]) {
    if (argc < 2) 
        printf("Usage: RSIP <string to reverse>\n");
    else {
        printf("String to reverse: %s\n", argv[1]);
        REVERSE(argv[1]);
        printf("Reversed string:   %s\n", argv[1]);
    }
    return 0;
}

Upvotes: 0

Davide Valdo
Davide Valdo

Reputation: 779

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.

Upvotes: 0

Oren
Oren

Reputation: 2807

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]);
  }
}

Upvotes: 0

Tool
Tool

Reputation: 12488

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?

Upvotes: 2

richardtallent
richardtallent

Reputation: 35373

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. ;)

Upvotes: 4

pau.estalella
pau.estalella

Reputation: 2243

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))

Upvotes: 0

Related Questions