Recursive Reverse Function

Question

I was wondering whether someone could explain how this small code snippet works.

void reverse(char *s)
{
   if(*s)
       reverse(s+1);
   else
       return;

   cout << *s;
}

When you call this function in main, it supposedly prints out the reverse of any string put in (ie. hello would cout as olleh) but I don't understand how. As I understand it, the if statement increases the value of s until it reaches the end of the string, printing out each value in the string as it goes. Why doesn't that just re-print the string. Clearly I am missing something. (Sorry btw, I am new to C++ and recursive functions)

Try hand-rolling a SHORT string ("cat" or "dog" springs to mind) through this function and record on paper, one step at a time, what happens. You may want to study up on pointer arithmetic first. — WhozCraig
– WhozCraig, Commented Aug 7, 2013 at 16:46
The thing you might be tripping up on is that the string has a \0 at the end, so there's an exit condition for the if statement. — Robert Harvey
– Robert Harvey, Commented Aug 7, 2013 at 16:49
@RobertHarvey I understand that there is an exit condition. However, doesn't that just mean *s is pointing to the last value in the string? How are the rest of the values printed out? — Sachin Weerasooriya
– Sachin Weerasooriya, Commented Aug 7, 2013 at 16:53

Sergey Kalinichenko · Accepted Answer · 2013-08-07 16:52:10Z

Consider how the "hello" string is stored in memory: let's say the address of its 'h' character happens to be 0xC000. Then the rest of the string would be stored as follows:

0xC000 'h'
0xC001 'e'
0xC002 'l'
0xC003 'l'
0xC004 'o'
0xC005 '\0'

Now consider a series of invocations of reverse: the initial invocation passes 0xC000; the call of reverse from inside the reverse passes s+1, so the next level gets 0xC001; the next one gets 0xC002, and so on.

Note that each level calls the next level, until the level that sees '\0'. Before we get to zero, the stack is "loaded" like this:

reverse(0xC004) // the last invocation before we hit '\0'
reverse(0xC003)
reverse(0xC002)
reverse(0xC001)
reverse(0xC000) // the earliest invocation

Now when the top invocation calls reverse(0xC005), the check for *s fails, and the function returns right away without printing anything. At this point the stack starts "unwinding", printing whatever is pointed to by its s argument:

0xC004 -> prints 'o', then returns to the previous level
0xC003 -> prints 'l', then returns to the previous level
0xC002 -> prints 'l', then returns to the previous level
0xC001 -> prints 'e', then returns to the previous level
0xC000 -> prints 'h', then returns for good.

That's how the reverse of the original "hello" string gets printed.

jrok · Accepted Answer · 2013-08-07 16:59:16Z

3

Try visualizing how the call stack builds up. Each recursive call creates another stack frame with a copy of s incremented by one. When the exit condition occurs, the stack starts unwinding and cout statement gets called for each frame. Because of LIFO principle, the string is printed in reverse.

enter image description here

answered Aug 7, 2013 at 16:59

jrok

55.5k10 gold badges114 silver badges146 bronze badges

Comments

Bernhard Barker · Accepted Answer · 2013-08-07 16:54:00Z

2

Let's consider a string of length 3. reverse(i) is short for the function called on the i-th index of the string (well technically it's the char pointer + i, but that explanation requires a little more advanced understanding).

It's also useful to note (as Robert pointed out) that *s returns false if s points to \0, which indicates the end of the string, so, in this case, it will simply return.

Here's what happens:

reverse(0)
  calls reverse(1)
    calls reverse(2)
      calls reverse(3)
        end of string - return
      prints 2
    prints 1
  prints 0

answered Aug 7, 2013 at 16:54

Bernhard Barker

55.7k14 gold badges111 silver badges143 bronze badges

Comments

sedavidw · Accepted Answer · 2013-08-07 16:51:04Z

1

Lets look at a simple example, assume s = "the"

We would have:

rev(t) ->increment pointer

rev(h)->increment pointer

rev(e) ->increment pointer

rev('\0') (this would just return)

Then we would be back in the body of rev(e) which would print e

Then back to rev(h) which would print h

Then finally back to rev(t) which would print t

In that order then we would have: eht ("the" in reverse)

answered Aug 7, 2013 at 16:51

sedavidw

11.8k18 gold badges70 silver badges103 bronze badges

Comments

dieram3 · Accepted Answer · 2013-08-07 16:58:18Z

0

Perhaps it would be clearer to write the function as:

void reverse(const char *s)
{
   if(*s)
   {
     reverse(s+1);
     std::cout << *s;
   }
}

i.e each not null characther will be printed after calling the next one (by the calling to reverse)

PD: Use "const char*" instead of "char*" if you will not modify the given string.

answered Aug 7, 2013 at 16:58

dieram3

5913 silver badges7 bronze badges

Collectives™ on Stack Overflow

Recursive Reverse Function

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related