Reversing a String

[JudyFaye]

I have this bit of code that reverses a string but there's a bit of it that I just don't understand:

int main()
{
	char sentence[20]; //Create char array

	void reverse( const char * const sPtr );

	printf( "Enter your text please: \n" );

	// Uses gets to read line of text
	gets( sentence );

	printf( "Your text in reverse is: \n");
	reverse( sentence );

	system( "PAUSE" );
	getchar();
	return 0;
}

void reverse( const char * const sPtr ){
	if( sPtr[ 0 ] == NULL){
		return;
	}

	else {
                reverse( &sPtr[ 1 ] );
		putchar( sPtr[ 0 ] );
	}
}

In the :
reverse( &sPtr[ 1 ] );
putchar( sPtr[ 0 ] );

I just don't get how this bit results in the entered string being reverse. Could someone clarify this for me please.

Also apologies it's been a while since I was on here so not sure how to make code look like code.

Cheers

[D80DSL3A]

The reverse function is recursive, ie. it calls itself.

void reverse( const char * const sPtr ){
if( sPtr[ 0 ] == NULL){
    return;// end of string reached. Stop calling yourself!
    }
    else {
        reverse( &sPtr[ 1 ] );// Call self and pass a pointer to the next character (reason for the 1)
        putchar( sPtr[ 0 ] );// tail recursion. Each character is printed as the function calls return
    }
}

The function calls keep going until the end of the string is reached. The calls then begin returning and one character is printed out as each call returns.

[Smac89]

reverse( &sPtr[ 1 ] );
putchar( sPtr[ 0 ] );

That bit you don't understand is the recursive call. The function will recursively call itself, and each recursive call creates a stack frame in the function call stack. If any of the words I am using now sound gibberish to you, you need to go and read about recursion.

When the recursion finishes, i.e. sPtr[ 0 ] == NULL, the recursion starts to unwind, i.e. the stack frames are popped off the call stack. And just before each stack frame is destroyed, we print (putchar( sPtr[ 0 ] );) the first character of the string at that stack frame.

Note that this prints the string in reverse and does not actually reverse the string. To reverse the string, you can do something like:

void reverse(char *sPtr ) {
    char *end;
    for(end = sPtr; *end != NULL; end++); // find the end of the string

    char *beg;
    for (beg = sPtr; beg < --end; beg++) {
        char temp = *beg;
        *beg = *end;
        *end = temp;
    }
}

[JudyFaye]

Right I got everything you guys said, except for one major thing: How does the
reverse( &sPtr[ 1 ] ) move to the next character. That's the main thing I just can't wrap my head around. Since to me that's just calling the address to the 2nd element ( or no 1 element depending on how you count ) and just churning that through the same function.

Recursion I have no issue understanding. putchar( sPtr[ 0 ] ) I know I will fully get when I understand the reverse specifically how is it doing what you just said with just &sPtr[ 1 ].

Also the putchar doesn't manipulate the array just printing whatever element it has.

[Smac89]

You need to understand what a pointer is and that an array is a pointer to a contiguous memory address. For example given the following expression:

int *v = new int[5];

v is not the "array", v is a pointer. The array/contiguous memory is this new int[5];. Why is this? I will try to explain

Memory

Everything exists in memory, and to be able to manipulate those things, we can either decide to go down to

the machine level and access memory by using registers to talk to the processor directly or we can declare variables (which can be interpreted by a computer) to hold reference to them, then manipulate those variables as we see fit. The later is what C++ makes use of.
But how does one hold reference to a chunk of memory? I'm sure you have at one point declared an array of over 100 elements, but did you also declare over 100 variables to hold reference to each position in the array? I think not and I hope not. This is what pointers are for.

Pointers

Pointers are smart (not to be confused with smart pointers) in that it realises that an array has a beginning

and (hopefully) an end, but we are most likely interested in the beginning. So when you do this int *v = new int[5];, v points to the one place that is well defined for a chunk of memory - i beginning.

Difference

Now you have a reference to a chunk of memory on the heap, so what can you do with this? The most

common thing to do with this chunk of memory is to index into it? What is indexing (pretend you just asked that question)? To the unenlightened user, indexing means to get the item in the array at a certain position. So when such a user tries to access this array, they think to themselves - "I'm just going to reach in there and grab something by putting the index between 2 square brackets i.e. cout << v[4] << endl". Wrong! Here is what the enlightened user will think.
"I want to get the item at index 5, but I only have a pointer pointing to index 0 - first item. So I will simply add 4 to the position of this pointer and retrieve the element at that position i.e. cout << *(v + 4)<< endl". Success! If you were not enlightened before reading this, now you are. Moving on.

Bring it all together

What does this have to do with your question? I had to make sure you knew the basics before taking it one

step further. Lets continue this with our initial array, say we have a function that takes an array but only makes use of the first 2 elements, Why? Beats me but this is just an example.
So we have this function:

int max(int *pair) {
    if (pair[0] >= pair[1]) return pair[0];
    return pair[1];
}

Now we realise that the values we actually want to pass to this function are the last 2 elements in our array. The unenlightened user will solve this by creating an array of 2 elements and copy over the elements we need into this new array and pass it to the function. But since we are enlightened (if you aren't go back and read paragraph 5), we see an opportunity to use a pointer to the start of the required position in our array (which is also an array). So to do this we actually have 2 ways:
One way is the way I already showed which is:
cout << max(v + 3) << endl;
But if we really wanted to confuse any unenlightened user and just make their life difficult ;), we adopt a familiar style but with a twist, namely:
cout << max(&v[3]) << endl;
What does this do? It does exactly the same thing as the first one does but in reverse. The first one will shift out pointer over by 3 positions and now the pointer is pointing to the address of the 4th element. The second one gets the item at index 3 and returns it's address which the compiler will create an implicit pointer for and passes this to the function.

Conclusion

So in regards to your function, you can see that it is just creating pointers to the first element of the array

for each recursion and only stops when this pointer reaches the null byte, in which case the recursion stops and putchar takes over by printing the first character each time which also happens to print the array in reverse

[JudyFaye]

Ah right so everytime the recursion occurs, with reverse( &sPtr[ 1 ]), the pointer shifts over and points to the address of the element that's the next one over. Then the pointer keeps moving over till there's a null value in the array and then the putchar happens and everything just happens again(sorta) in reverse order hence why the function can print the array in reverse order (seemingly by manipulating the array) but with out tinkering with the array directly just by grabbing the address of the elements.

Excuse me if I sound like a complete noob. I'm still kinda wrapping my head around pointers.

[BasV]

I hope this'll help you understand better: See this as the order every relevant part of the reverse function is being called. Note that every string ends in a NULL character, which is equivalent to '\0'.

reverse("hello\0") {
 reverse("ello\0") {
  reverse("llo\0") {
   reverse("lo\0") {
    reverse("o\0") {
     reverse("\0") {
      ->return // because the current character is \0 (NULL)
     }
     ->print("o")
    }
    ->print("l")
   }
   ->print("l")
  }
  ->print("e")
 }
 ->print("h")
}

Cheers!