9

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?

Improve this question
4
  • 1
    I suspect an upcoming assignment will be about binary trees (and maybe their implementations as AVL and red black trees...). Commented Feb 18, 2015 at 20:44
  • @MichaelT anything you would recommend I look at before that possible assignment would come up? Commented Feb 18, 2015 at 20:45
  • Unsurprising? pow(2, 14) == 16384 Commented Feb 18, 2015 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. Commented Feb 18, 2015 at 21:07

2 Answers 2

Reset to default
13

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.

Improve this answer
4
  • 1
    Note the OP is writing in Java, which does not support tail call recursion in general Commented Feb 19, 2015 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. Commented Feb 19, 2015 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 Commented Feb 19, 2015 at 2:45
  • @raptortech97: Read c2.com/cgi/wiki?TailRecursion for more information. Commented Feb 19, 2015 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".

Improve this answer
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. Commented Feb 19, 2015 at 2:47

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.