Question

Q1:

The sorted values array contains the sixteen integers 1, 2, 3, 13, 13, 20, 24, 25, 30, 32, 40, 45, 50, 52, 57, 60. How many recursive calls are made by our binarySearch method, given an initial invocation of binarySearch(25, 0, 15)?

Answer Choices :

3

   

2

   

4

   

0

   

1

Q2:

The sorted values array contains the sixteen integers 1, 2, 3, 13, 13, 20, 24, 25, 30, 32, 40, 45, 50, 52, 57, 60. How many recursive calls are made by our binarySearch method, given an initial invocation of binarySearch(24, 0, 15)?

Answer Choices :

1

   

4

   

2

   

3

   

0

Q3:

The number of recursive calls that a method goes through before returning is called:

Answer Choices:

combinatorial recursive count.

   

activation stack frame.

   

the depth of recursion.

   

order of growth efficiency.

Q4:

All programming languages support recursion.

Group of answer choices:

True

False

Answer 1

Q1. The answer is 0.

It is because in the process of binary search we find the low,high index of the sorted array. Then we find the mid value

ie. mid =( low +high)/2

If the mid value represents the number we are searching, then we stop. So no need for further checking and no recursive call. In the above case low=0, high=15 so mid=(0+15)/2 = 7.5=7(round off to smallest integer value)

At the index 7 we have 25 , that is we found what we are searching. So no recursive call . Answer 0

Q2. The answer is 3.

All the rules and formula applies as above.

step1: mid= (0+15)/2=7.5=7

value at 7 is 25 ie grater than 24(we are searching). so low=0,high=mid-1=7-1=6

RECURSION 1

step2: mid=(0+6)/2=3

value in 3 =13 is lower than 24 . so low=mid+1= 3+1=4, high=6

RECURSION 2

step3:mid= (4+6)/2=5

value(5)=20 is less than 24. low=5+1=6, high=6

RECURSION 3

step4: mid=(6+6)/2=6

value at 6= 24.

So we can stop.

So the no oof recursive call is 3

Q3. The no of recursive calls that is taken before returning is called the depth of recursion