CODEWITHSUNDEEP
crecursion
tempy
tempy

Reputation: 907

How does this string reverse recursion work?

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.

Upvotes: 0

Views: 852

Answers (3)

user711413
user711413

Reputation: 777

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.

Upvotes: 0

epsalon
epsalon

Reputation: 2294

This code is extremely inefficient but what it does is:

  1. Save the original first character
  2. Recursively reverse the rest of the string (string+1 is a pointer to the second character in the string).
  3. Copy the rest of the (reversed) string one character to the left.
  4. 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--:
  }
}

Upvotes: 2

Petr Baudis
Petr Baudis

Reputation: 1198

*(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.

Upvotes: 0

Related Questions