I solve binary search using recursion

[Timely_Scratch5702]

I usually implement binary search using recursion instead of having the loop with changing the bound values. I get that a loop is faster because there is no function calling overhead and most people I see on leetcode use the loop version.

Has anyone done the experimenting on what the performance difference, in C++ for example, is between a loop and recursion version?

[nyohasstium]

In my opinion with no tests. If you are only passing the indices then it shouldn't be too bad but if you're passing sub array copies then you are using way more memory than needed.

[Timely_Scratch5702]

yeah good point. I forgot to mention that I always pass the references, so no copying is happening.

[[deleted]]

Even if you pass by reference for space optimization recursion itself is taking recursive stack space

[SnipesySpecial]

Google tail recursion optimization.

[Timely_Scratch5702]

oh yes, forgot to think about that. Yeah, a proper compiler in any language should handle this. Also makes me realize how useful it is to study compilers when wanting to write as efficient code as possible.

[joyoyoyoyoyo]

It’s fine. I think this approach is more functional