‹ 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);
}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).