0

Please need to know how this reverse function work, don't really get it, I know pointer do point to string[0], but how this function is able to print the right character to reverse the string correctly, How this is archive?

#include <iostream>
using namespace std;

void reverse(char *s); //prototype
//-------------------------------------------------------------------       
int main ()
{
    char str[] = "begin_this is a test_last";    //cstring to be reverse

    reverse(str);    //recursive function

    cout << "\n";

    return 0;
}
//--------------------------------------------------------------------- 
void reverse(char *s)               
{                                   
    if(*s){                         
        reverse(s + 1);
    }else
        return;
    cout << *s;   //question how this print the string in reverse??????
}
Force BeWhithYou
  • 3
  • 1

3 Answers3

3

Your reverse() function is not actually reversing the string in memory, it is just outputting the string's characters in reverse order (to actually reverse the string in memory, use the STL's std::reverse() algorithm).

Now, lets look at the logic.

main() calls reverse(). A stack frame is pushed on the call stack, where s is pointing at the 1st character (str decays into a pointer to the first character).

s is not pointing at the null terminator, so reverse() calls itself, pushing a new stack frame on the call stack, where s contains a pointer to the 2nd character.

s is not pointing at the null terminator, so reverse() calls itself again, pushing a new stack frame on the call stack, where s contains a pointer to the 3rd character.

And so on, until reverse() is running with a stack frame where s is pointing at the null terminator. At this point, nothing has been output to std::cout yet, and a pointer to every character, including the null terminator, has been pushed onto the call stack in first-to-last order.

call stack

Now, reverse() stops calling itself and just exits, popping the current stack frame from the call stack (where s points at the null terminator).

Execution returns to the previous call site of reverse(), whose stack frame has s pointing at the last character. That character is output to std::cout and then reverse() exits, popping that stack frame from the call stack.

Execution returns to the previous call site of reverse(), whose stack frame has s pointing at the 2nd-to-last character. That character is output to std::cout and then reverse() exits, popping that stack frame from the call stack.

Execution returns to the previous call site of reverse(), whose stack frame has s pointing at the 3rd-to-last character. That character is output to std::cout and then reverse() exits, popping that stack frame from the call stack.

And so on, until execution returns to main(), and the entire string has been output to std::cout in reverse order.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
  • Thanks for your time, I guess this recursive do loop calling herself, but main only call for it one time, and the cout statement, is only executed by an else, I only see it, executing when the NULL is hit and at this point s pointer is at 'l' position of the string, at this point, I forseek the call to cout because the NULL condition is met, but how the pointer jump from NULL, my cycle in my mind, is original call with string[0], recursive call string[0+n], but all this time is not cout anything till the last string[last], original,. – Force BeWhithYou Aug 04 '17 at 03:22
  • will generate a call to the recursive function inside which will be pointing to string[NULL], and now will trigger the else and the cout, I know that my approach is wrong in some point, but where.. – Force BeWhithYou Aug 04 '17 at 03:22
  • @ForceBeWhithYou: what exactly was unclear about what I explained to you? I explained exact how the code moves through the string from first-to-last and then prints the characters last-to-first. Do you understand what the call stack is, and how stack frames work? And how the `__cdecl` calling convention interacts with the call stack? If not, you have more learning to do before you can tackle recursion (and why it can be dangerous for long iterations) – Remy Lebeau Aug 04 '17 at 03:26
  • I do have some understanding of the stack functionality, now and your explanation was well understood with a brilliant concept, what is hard for me is to combine, this functionality with the else, who does the cout. I never have a problem understanding recursion, with number, and arithmetic, but this concept draining out of the else statement hit me hard, thanks for you time I will consult your recommended routine _cdecl – Force BeWhithYou Aug 04 '17 at 20:47
  • @ForceBeWhithYou: re-write `reverse()` to remove the `else`, maybe it will make more sense to you: `void reverse(char *s){ if (*s == 0) { return; } reverse(s + 1); cout << *s; }` Do you understand what `return` actually does? And how calling a function blocks the caller until the function exits, and then the caller picks up where it left off? – Remy Lebeau Aug 04 '17 at 21:08
2

reverse(char *s) is a recursive function. Recursive function would terminate only if certain conditions are met. In your example, the condition is *s == NULL

If the condition does not met, it would uses a stack to save the content of current function and execute the remaining code until its next generation complete all the tasks.

In your example, all cout << *s would be push into the stack until the last generation. Therefore, the first time you execute cout << *s is actually printing the last character of your string.

For example, let char arr[] = "READ" be the array. 

1st   R  // waiting
2nd   E  // waiting
3rd   A  // waiting
4nd   D  // printing!!

After the last generation is complete:

1st   R  // waiting
2nd   E  // waiting
3rd   A  // printing!!
4nd   D  // finish!!

And then the next generation

1st   R  // waiting
2nd   E  // printing!!
3rd   A  // finish!!
4nd   D  // finish!!

And then the final generation

1st   R  // printing!!
2nd   E  // finish!!
3rd   A  // finish!!
4nd   D  // finish!!

This is exactly how to print a string backwards recursively.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Shiu Chun Ming
  • 227
  • 2
  • 13
  • This is exactly what I see, no other cycle hit NULL, till the last character of the string is call, and because the function is using s + 1, met the NULL, criteria, from there, how the other character are hit by cout, you explaining to me, they has being in the stack, and print recursive, but I don't see, when the condition is met, to print A in your READ example – Force BeWhithYou Aug 04 '17 at 23:28
  • I get the stack thing, but , I don't see it when it need to be used to store A, just D. and the function end right there in my cycles. – Force BeWhithYou Aug 04 '17 at 23:43
  • Men I when to the debugger and see, those call, to the stack, repeating, the cout statement wicked thank guys. – Force BeWhithYou Aug 04 '17 at 23:52
2

Translated into English: in order to print a string in reverse, you first reverse-print everything except its first character, then you print its first character. If the string is empty, you do nothing.

Recursion, like the idea of functions in general, is older than computers. You can understand it without knowing a single thing about how a programming language might be implemented.
(It helps if you're familiar with mathematical induction, but it's definitely not a requirement.)

In fact, if you understand that in order to "first do this, then do that", that has to wait until this is done, you've pretty much understood everything.

The only thing missing, and what makes it recursive, is that in order to accomplish this, you may possibly need to do a smaller bit of "this, then that" first.

More concretely, suppose we want to print "abc" in reverse.

One way to look at it as that we need to first print 'c', then 'b', then 'a'.

Another way is to say that we can first print "cb", then 'a'.
But "cb" is also the reverse of the "tail" of "abc", so we should be able to use the same procedure for reversing both "abc" and "bc" - as long as we know how to reverse a shorter string, we can do that and then tack the string's first character on afterwards.
When does it end?
When we reach the shortest possible string, the empty string, we don't need to do anything, so that's where it ends.

Slightly more formally, we can use this procedure:

  • If the string is empty, do nothing.
  • If the string is not empty:
    • First print, using this procedure, all the characters except the first one,
    • Then print the first character.

and reversing "abc" will go like this:

   Reverse "abc"
-> Reverse "bc", then print 'a'
-> Reverse "c", then print 'b', then print 'a'
-> Reverse "", then print 'c', then print 'b', then print 'a'

Reversing "" is to not do anything. 
After we've done nothing, we can continue executing the rest of the sentence.

-> print 'c', then print 'b', then print 'a'
   [Output: c]
-> print 'b', then print 'a'
   [Output: cb]
-> print 'a'
   [Output: cba]
molbdnilo
  • 64,751
  • 3
  • 43
  • 82