How does this string reverse recursion work?

Question

I usually understand recursions pretty well, but because I'm new to C functions like strcpy and pointers I couldn't figure out how this recursion reverses a string:

char *reverse(char *string)
{
    if (strlen(string) <= 1)
        return string;

    else
    {
        char temp = *string;

        strcpy(string, reverse(string+1));

        *(string+strlen(string)) = temp;

        return string;
    }
}

The strcpy part seems a little bit complicated to me, and also what's the purpose of this line:
*(string+strlen(string)) = temp;?

I realize that after flipping the string you need to add the character that was at the beginning to the end of the string, but I'm not sure I understand the logic behind this code.

The strcpy() is dangerous here, since destination and source can overlap. Memmove() would be appropriate. (but harder to get right) — wildplasser
– wildplasser, Commented Sep 30, 2012 at 17:12

epsalon · Accepted Answer · 2012-09-30 17:16:09Z

2

This code is extremely inefficient but what it does is:

Save the original first character
Recursively reverse the rest of the string (string+1 is a pointer to the second character in the string).
Copy the rest of the (reversed) string one character to the left.
Put the original first character at the end (*(string+strlen(string)) = temp;).

The *(string+strlen(string)) = temp; is equivalent to string[strlen(string)] = temp; if that is easier to understand.

I will not recommend using this code at all, since it is extremely inefficient -- it copies the entire string (and measures its length twice) in every iteration, not to mention waste stack space.

A much better implementation would be:

void reverse(char *s) {
  char *e = s+strlen(s)-1;
  while (e > s) {
    char tmp = *s;
    *s=*e;
    *e=tmp;
    s++; e--:
  }
}

edited Sep 30, 2012 at 17:16

answered Sep 30, 2012 at 17:08

epsalon

2,30413 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

tempy Over a year ago

But if I send a pointer to "ABC", then after string points to "BC", it is changed to CC - string+strlen(string) points to the zero terminator, isn't it? shouldn't it be string+strlen(string)-1?

epsalon Over a year ago

Yes, except the strcpy also copied the null terminator, moving it one place back, shortening the string. Again, very dangerous and inefficient.

tempy Over a year ago

Thank you for your help; the implementation you added makes much more sense to me.

Petr Baudis · Accepted Answer · 2012-09-30 17:05:42Z

0

*(string+strlen(string)) = temp is so-called pointer arithmetic - that code is equivalent to string[strlen(string)] = temp. Therefore, this puts the temp character to the end of the string. Note that the string still remains zero-terminated as reverse() returns string of the same length as its argument.

The reverse(string+1) is again pointer arithmetic, this time same as reverse(&string[1]) - i.e., reverse() will mirror the string from the second character onwards, but then strcpy() will place it at the beginning of the string, overwriting the first character that is stored in temp and put at the end of the string.

However, the overall code looks needlessly convoluted and inefficient, so I'd think twice before drawing any lessons on how to do things from it.

answered Sep 30, 2012 at 17:05

Petr Baudis

1,1988 silver badges13 bronze badges

1 Comment

tempy Over a year ago

Thank you for your help. It's surprising me because it's an exercise from a C programming book written by someone from Microsoft.

user711413 · Accepted Answer · 2012-09-30 17:24:36Z

0

This is how the code works. The input string is divided in two parts, the first character, and the rest. The first character is stored in temp, and the rest is reversed through a recursive call. The result of the recursive call is placed at the beginning of the result, and the character in temp is placed at the end.

string is [1234567890]

temp is 1, string+1 is [234567890]

reverse(string+1) is [098765432], temp is 1

the strcopy line is the part that copies the result from reverse(string+1) at the beginning of string, and *(string+strlen(string)) = temp is the part that copies temp at the end of string.

answered Sep 30, 2012 at 17:24

user711413

7975 silver badges12 bronze badges

Collectives™ on Stack Overflow

How does this string reverse recursion work?

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related