C++ Understanding recursive function

Question

I need some help with understanding this recursive function. It is returning 101 when n = 5 but I do not understand why. Here is the function:

string RecursiveMystery(int n) {
  string s = "1";
  if (n % 2 == 0) {
    s = "0";
  }
  if (n < 2) {
    return s;
  }
  return RecursiveMystery(n / 2) + s;

So when RecursiveMystery(5), it should go into the end return function RecursiveMystery(5 / 2) which is equal to 0 + 1 which is 01 (because s = 1 at the time of RecursiveMystery(5)). I'm stuck with understanding how it is still returning 101.

Try to step in with a debugger, and you'll understand what's going on. There are 3 calls, with parameters: 5, 2 and 1. Only one is even, so the output is 101 (if printed) — vsoftco
– vsoftco, Commented Dec 10, 2014 at 20:18
You should read about tail recursion - cs.stackexchange.com/questions/6230/what-is-tail-recursion — ajmartin
– ajmartin, Commented Dec 10, 2014 at 20:24

Jakube · Accepted Answer · 2014-12-10 20:21:03Z

5

If you call RecursiveMystery(5), it returns RecursiveMystery(2) + "1". So we have to evaluate RecursiveMystery(2), which returns RecursiveMystery(1) + "0". And RecursiveMystery(1) returns `"1".

Therefore

RecursiveMystery(5) = RecursiveMystery(2) + "1" = RecursiveMystery(1) + "0" + "1" = "1" + "0" + "1" = "101"

Some more infos about the RecursiveMystery-method. It computes the binary representation of the number n. Basically it writes a 1 at the end, if n is odd, and a 0, if n is even. And n/2 is just the number n without the last digit (in binary representation ).

answered Dec 10, 2014 at 20:21

Jakube

3,6024 gold badges26 silver badges44 bronze badges

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

2 Comments

andayn Over a year ago

Since RecursiveMystery(2) returns a "0" wouldn't it be 01 since you can't add strings like you would int? Therefore shouldn't the return value be 01 (just for RecursiveMystery(2) + "1").

Jakube Over a year ago

RecursiveMystery(2) = RecursiveMystery(1) + "0" = "10"

Loki Astari · Accepted Answer · 2014-12-10 20:29:06Z

Stage 1:

Run the function with the different inputs you need to see what the results are:

RecursiveMystery(5)
    return RecursiveMystery(2) + "1";   // Gets to recursive call

// So look at what RecursiveMystery(2) does
RecursiveMystery(2)
    return RecursiveMystery(1) + "0";   // Gets to recurive call

// So look at what RecursiveMystery(1) does
RecursiveMystery(1)
    return "1";                         // Return early as n < 2

Stage 2

So now lets expand the top level manually

    RecursiveMystery(5)
        return RecursiveMystery(2) + "1";

=>   RecursiveMystery(5)
        return RecursiveMystery(1) + "0" + "1";

=>   RecursiveMystery(5)
        return "1" + "0" + "1";

=>   RecursiveMystery(5)
        return "101";

didierc · Accepted Answer · 2014-12-10 20:25:57Z

0

Your function starts out at 5, and keeps s as "1", then calls recursively with n = 2, and turns s to "0", then calls itself recursively one more time (because 2 is not below 2), with n as 1. And this time it's the last call, with s remaining "1".

Unwinding the calls back to the original one, you get "1"+"0"+"1".

answered Dec 10, 2014 at 20:25

didierc

14.8k3 gold badges35 silver badges52 bronze badges

Comments

Steve · Accepted Answer · 2014-12-10 22:05:19Z

0

if you want it to return "01" change the if statement

from

if (n < 2)

to

if (n <= 2)

answered Dec 10, 2014 at 22:05

Steve

1,46110 silver badges13 bronze badges

Collectives™ on Stack Overflow

C++ Understanding recursive function

4 Answers 4

2 Comments

Stage 1:

Stage 2

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Stage 1:

Stage 2

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related