Recursive and Iterative Binary Search: Which one is more efficient and why?

• With regard to time complexity, recursive and iterative methods both will give you O(log n) time complexity, with regard to input size, provided you implement correct binary search logic.
• Focusing on space complexity:
  • The iterative approach is more efficient since we are allocating a constant amount O(1) of space for the function call and constant space for variable allocations.
  • There have been concerns around the recursive version regarding the function stack it is going to use. However, once you see it carefully, the recursive version is a tail recursion. Most of the modern compiler converts the tail recursion into iterative program. Thus, there won’t be any issue regarding the usage of the function stack.

P.S. A tail recursion is also a kind of recursion but it will make the return value of the recursion call as the last statement of the method. This will make the calculation occurs before the recursion call and hence there is no need to keep the stack to store the intermediate value when it moves to the next recursive call.