Prashnikaप्रश्निका
Code
About
‹ Back to the paper

Question 3

5 marks

Computer ScienceISC 2020 Computer Science Paper 1OutputRecursion

What is the output of the following code?

The following function check( ) is a part of some class. What will the function check( ) return…

The following function check( ) is a part of some class. What will the function check( ) return when the value of (i) n=25 and (ii) n=10. Show the dry run/ working.
int check(int n)
{
    if(n<=1)
        return 1;
    if( n%2==0)
        return 1 + check(n/2);
    else
        return 1 + check(n/2 + 1);
}
Open in the Recursion visualiser

Answer

Answer

Dry run for n = 25: check(25): 25 is odd, so return 1 + check(25/2 + 1) = 1 + check(13) check(13): odd, so 1 + check(13/2 + 1) = 1 + check(7) check(7): odd, so 1 + check(7/2 + 1) = 1 + check(4) check(4): even, so 1 + check(2) check(2): even, so 1 + check(1) check(1): n <= 1, so return 1 Unwinding: check(2) = 1 + 1 = 2; check(4) = 1 + 2 = 3; check(7) = 1 + 3 = 4; check(13) = 1 + 4 = 5; check(25) = 1 + 5 = 6 Return value for n = 25: 6 Dry run for n = 10: check(10): even, so 1 + check(5) check(5): odd, so 1 + check(5/2 + 1) = 1 + check(3) check(3): odd, so 1 + check(3/2 + 1) = 1 + check(2) check(2): even, so 1 + check(1) check(1): returns 1 Unwinding: check(2) = 2; check(3) = 1 + 2 = 3; check(5) = 1 + 3 = 4; check(10) = 1 + 4 = 5 Return value for n = 10: 5 (i) n = 25 returns 6; (ii) n = 10 returns 5 (verified by running the code).