Q[Recursion]
If binary search technique uses recursion instead of iteration, the code:

i. will contain two base cases.

ii. will contain two recursive cases.

iii. when executed will lead to an exception, stack overflow.

Which of the above is valid?

Explanation:

Binary Search can be implemented using recursion. In recursive binary search, the array is repeatedly divided into two halves until the element is found or the search space becomes empty.

Understanding Each Statement:

• Statement i: "will contain two base cases."
  This statement is correct. Recursive binary search generally contains two base cases:
  • The element is found.
  • The search interval becomes invalid (low > high).
• Statement ii: "will contain two recursive cases."
  This statement is also correct. Binary search recursively searches:
  • The left half of the array.
  • The right half of the array.
  Therefore, there are two recursive cases.
• Statement iii: "will lead to stack overflow."
  This statement is incorrect. Binary search reduces the problem size by half in every recursive call. Therefore, recursion depth remains very small:
  
  Example:
  • For 1024 elements, recursion depth is only 10.
  Since the recursion depth is very low, stack overflow normally does not occur.

Conclusion:

Statements i and ii are correct. Therefore, the correct answer is: (a) i and ii