C++ Recursion

Hi,

 

I'm enrolled on a 3rd year BSc Computing Science degree and currently undertaking a module 'Algorithms & Collections'. I have been given the task to map out the activation records for the following piece of code:

int mystery(int n)
{
 
   // Base Case
   if (n <= 0) { return 0; }

   // Recursive (general) case
   return mystery( n / 2 ) + 1;

}

However, what I am confused about, is how the answer is 5?

 

If anyone could help me understand this it would be greatly appreciated!

 

Edit: My apologies, I meant, I can't seem to get why the answer would be 5 upon invoking mystery(20)? 

Edited by martintaylor1635, 11 March 2021 - 01:17 PM.

Greetings martintaylor,

If you write out the entire call chain (i.e. how the code would execute), you would get something like this:

mystery(20/2) + 1 =>

(mystery (10/2) + 1) + 1 =>

((mystery(5/2) + 1) + 1) + 1 =>

(((mystery(2/2) + 1) + 1) + 1) + 1 =>

((((mystery(1/2) + 1) + 1) + 1) + 1) + 1 =>

((((0 + 1) + 1) + 1) + 1) + 1

Bascially, each recursive call simply gets replaced with (mystery(N/2) + 1). Following this through, 1+1+1+1+1 = 5. Since your code shows int types, you're doing integer division. Integer division always results in 0 if the divisor (bottom number - in your case 2) is greater than the dividend.

Greetings martintaylor,

If you write out the entire call chain (i.e. how the code would execute), you would get something like this:

mystery(20/2) + 1 =>

(mystery (10/2) + 1) + 1 =>

((mystery(5/2) + 1) + 1) + 1 =>

(((mystery(2/2) + 1) + 1) + 1) + 1 =>

((((mystery(1/2) + 1) + 1) + 1) + 1) + 1 =>

((((0 + 1) + 1) + 1) + 1) + 1

Bascially, each recursive call simply gets replaced with (mystery(N/2) + 1). Following this through, 1+1+1+1+1 = 5. Since your code shows int types, you're doing integer division. Integer division always results in 0 if the divisor (bottom number - in your case 2) is greater than the dividend.

 

 

Thank you Jake,

 

I really appreciate your time! That helped me a lot to understand it!

 

Regards,

Martin