What benefit is there to using recursive binary search over iterative binary search or vice versa?

Question

In a recent assignment for my programming 2 class we tested the efficiency of searches by populating a java ArrayList with 13,040 strings. The sequential search was obviously slower than the binary searches due to the complexity difference and the amount of times the code actually has to loop through the code.

Iterative binary search and recursive binary search, however, had the same amount of comparisons. For example:

sequentialSearch(): 'some_word' found in ArrayList at index 13,020 - comparisons: 13,021

The comparisons being how many times the computer actually checked if the user's "some_word" was equal to a value ArrayList.

iterativeBinarySearch(): 'some_word' found in ArrayList at index 13,020 - comparisons: 14
recursiveBinarySearch(): 'some_word' found in ArrayList at index 13,020 - comparisons: 14

So if the comparisons of iterative and recursive are the same, in what situations would you choose one over the other? Is it simply personal taste or is there a specific reasoning for using a specific one?

Answer 1

If your language processor (compiler or interpreter) properly implements tail recursion optimization, then there winds up being no difference between a properly-coded tail-recursive binary search and an iterative binary search. The language processor will turn the recursive calls into simple loops.

At that point, choice of recursive vs. iterative formulation is pretty much a matter of personal and local preference. Some people find recursive code easier to understand. Some people are scared to death of recursion, or don't understand it, or have no clue about tail recursion optimization, and want explicitly iterative code everywhere.

Answer 2

After more research, I have created some pros/cons on each algorithm. It's easier to visualize in a table, but that is currently seemingly unsupported by markdown. However, I've separated these pros/cons into 6 categories (Structure, Control, Condition, Update, Speed, and Space).

Depending on the project at hand this should be able to determine the best algorithm to practice.

---

Iterative

---

Structure - Repetition
Control - Explicit use of loop
Condition - Entrance Condition
Update - It is controlled by counter and keeps updating a counter
Speed - It usually runs faster than recursive
Space - It usually takes less space than recursive.

---

Recursive

---

Structure - Selection
Control - Recursive call (i.e. recursive case). Data becomes smaller each time it is called.
Condition - Exit Condition (i.e. base case)
Update - It gradually approaches to base case. It keeps producing smaller versions at each call.
Speed - It usually runs slower than iterative
Space - It usually takes more space than iterative, called "call-stack".

---