Читать книгу Algorithms For Dummies - John Paul Mueller, John Mueller Paul, Luca Massaron - Страница 97

Recursion is part of many different algorithmic programming solutions, as you see in the upcoming chapters. In fact, it’s hard to get away from recursion in many cases because an iterative approach proves nonintuitive, cumbersome, and time consuming. However, you can create a number of different versions of the same solution, each of which has its own characteristics, flaws, and virtues.

The solution that this chapter doesn’t consider is sequential search, because a sequential search generally takes longer than any other solution you can employ. In a best-case scenario, a sequential search requires just one comparison to complete the search, but in a worst-case scenario, you find the item you want as the last check. As an average, sequential search requires (n+1)/2 checks or O(n) time to complete. (The “Working with functions” section of Chapter 2 tells you more about big-O notation.)

The binary search in the previous section does a much better job than a sequential search does. It works on logarithmic time or O(log n). In a best-case scenario, it takes only one check, as with a sequential search, but the output from the example shows that even a worst-case scenario, where the value doesn’t even appear in the list, takes only six checks rather than the 21 checks that a sequential search would require.

If you look at performance times alone, however, the data you receive can mislead you into thinking that a particular solution will work incredibly well for your application when in fact it won’t. You must also consider the kind of data you work with, the complexity of creating the solution, and a host of other factors. That’s why later examples in this book also consider the pros and cons of each approach — the hidden dangers of choosing a solution that seems to have potential and then fails to produce the desired result.