CODEWITHSUNDEEP
c++recursion
user2302335
user2302335

Reputation: 145

Not sure what this recursive function returns

I am reading about recursive functions, and I have been trying to figure out the mathematical formula for this one. I thought maybe it was a logarithmic function, but that does not seem to be it. If anyone could point me in the right direction, I would appreciate it.

unsigned f(unsigned n){
    if(n<2)
    return 1;

    return 1 + f(n/2);
}

Upvotes: 1

Views: 170

Answers (5)

Tony Delroy
Tony Delroy

Reputation: 106096

I know you said "mathematical function" and that's set the perspective for existing answers, but to show another perspective, it returns:

  • number of bits needed to store n (if you consider 1 bit necessary to meaningfully encode number 0 distinct from no number at all)
  • 1-based index of the most significant bit set in n|1, aka
  • minimum of (1) and (the 1-based index of the most significant bit set in n)

Sometimes when you're looking at code it can help to see that a function could be used with different intent - either perspective might make it easier to understand the context of use.

Upvotes: 1

taocp
taocp

Reputation: 23634

Since you are concerned about the math formula that the function is based on:

Here it is: f is a function of n:

f(n) = 1 + f(n/2) if n >=2
f(n) = 1          if n <=1  //n is unsigned so n >=0

With the above formula in mind, the underlying algorithm then have logarithmic complexity. The reason is that at every step, it will reduce the size of n by half and it will take log(n) (base 2) steps to reach 1, therefore, it is logarithmic complexity with O(logn).

Upvotes: 1

Yuushi
Yuushi

Reputation: 26040

It is a logarithm function, just to the base 2. More specifically, it's the ceil 1 + floor(log2(n)).

Upvotes: 4

Mike Woolf
Mike Woolf

Reputation: 1210

More precisely, this implements floor(logbase2(n))

Upvotes: 0

Syntactic Fructose
Syntactic Fructose

Reputation: 20076

This function returns the number of times the function executes by dividing the whole number by 2 until reaching zero

EX:

f(8)-

return f(4) //continue on
return f(2) //continue on
return f(1) //we know this is 1
return f(2) //now we can do this one, 2
return f(4) //and this one, 3

Upvotes: 0

Related Questions