8

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?

4
  • 1
    I suspect an upcoming assignment will be about binary trees (and maybe their implementations as AVL and red black trees...). – user40980 Feb 18 '15 at 20:44
  • @MichaelT anything you would recommend I look at before that possible assignment would come up? – Jaken Herman Feb 18 '15 at 20:45
  • Unsurprising? pow(2, 14) == 16384 – rwong Feb 18 '15 at 20:47
  • @JakenHerman trees (binary). Possibly some other types of trees too, but those can rapidly get confusing unless you have a firm foundation on trees in the first place. Binary trees are the simplest of them. – user40980 Feb 18 '15 at 21:07
11

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.

4
  • 1
    Note the OP is writing in Java, which does not support tail call recursion in general – raptortech97 Feb 19 '15 at 2:40
  • My understanding is that the JVM does not support a general GOTO operation, which is necessary for general tail call optimization. Tail recursion is a special case of tail call. – John R. Strohm Feb 19 '15 at 2:43
  • I suppose that certain cases could be optimized, but I don't know of a JDK that does that, so the point still partially stands – raptortech97 Feb 19 '15 at 2:45
  • @raptortech97: Read c2.com/cgi/wiki?TailRecursion for more information. – John R. Strohm Feb 19 '15 at 8:30
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".


1
  • 1
    Binary search is tail-recursive, not generally recursive. As such, a recursive implementation should, given a competent language processor, incur NO speed or stack space penalty over an iterative implementation. Read the "Lambda: The Ultimate ..." papers from the MIT AI Lab for the gory details. – John R. Strohm Feb 19 '15 at 2:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.