CODEWITHSUNDEEP
c++
andayn
andayn

Reputation: 97

C++ Understanding recursive function

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.

Upvotes: 2

Views: 127

Answers (4)

Steve
Steve

Reputation: 1421

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

from

if (n < 2)

to

if (n <= 2)

Upvotes: 0

Loki Astari
Loki Astari

Reputation: 264351

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";

Upvotes: 1

didierc
didierc

Reputation: 14730

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".

Upvotes: 0

Jakube
Jakube

Reputation: 3565

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 ).

Upvotes: 5

Related Questions