In this chapter, we concentrate on some key aspects of computer science thinking that go beyond programming fundamentals. Our focus on performance issues is a nice way to transition into the data science chapters, where we’ll use AI and big data techniques that can place extraordinary performance demands on a system’s resources.
We begin with a treatment of recursion. Recursive functions (or methods) call themselves, either directly or indirectly through other functions (or methods). Recursion can often help you solve problems more naturally when an iterative solution is not apparent. We’ll show examples and compare the recursive programming style to the iterative style we’ve used to this point. We’ll indicate where each might be preferable.
Next, we’ll look at the crucial topics of searching and sorting arrays and other sequences. These are fascinating problems, because no matter what algorithms you use, the final result is the same. So you’ll want to choose algorithms that perform "the best"—most likely, the ones that run the fastest or use the least memory. For big data applications, you’ll also want to choose algorithms that are easy to parallelize. That will enable you to put lots of processors to work simultaneously—much as Google does, for example, when answering your search queries quickly.
This chapter focuses on the intimate relationship between algorithm design and performance. You’ll see that the simplest and most apparent algorithms often perform poorly and that developing more sophisticated algorithms can lead to superior performance. We introduce Big O notation, which concisely classifies algorithms by how hard they have to work to get the job done. Big O helps you compare the efficiency of algorithms.
In an optional section at the end of this chapter, we develop an animated visualization of the selection sort so you can see it "in action." This is a great technique for understanding how algorithms work. It can often help you develop better performing algorithms.
The chapter includes a rich selection of recursion, searching and sorting exercises. You’ll attempt some of the classic problems in recursion, implement alternative searching and sorting algorithms, and build animated visualizations of some of these to better understand the deep ties between algorithm design and performance.