Chapter 14
Recursion
14.1 Base Case and General Case ........................................................... 319
14.2 Dynamic Programming ................................................................. 321
14.3 Internal Details of a Recursive Call .................................................... 323
14.4 Array Algorithms ....................................................................... 326
14.4.1 Binary Search ................................................................... 326
14.4.2 Bubble Sort ..................................................................... 329
14.4.3 Selection Sort ................................................................... 331
14.4.4 Insertion Sort ................................................................... 333
14.4.5 Quick Sort ...................................................................... 334
14.4.6 Merge Sort ...................................................................... 336
14.5 Summary ................................................................................ 338
14.6 Syntax .................................................................................. 338
14.7 Important Points ....................................................................... 338
14.8 Exercises ................................................................................ 339
14.9 Lab ...................................................................................... 340
14.10 Project .................................................................................. 340
This chapter introduces the reader to the advanced topic of recursion. Recursion is when
a method calls itself. Recursive algorithms try to break a complex problem into smaller
versions of the same problem, where the smaller versions are solved in the same way (i.e.,
by breaking them further into smaller problems). Of course, this process should not continue
inﬁnitely and at some point the problem should become simple enough so that it can be
solved directly (we will refer to this as the base case of the recursive program).
Although a powerful tool, a recursive algorithm is not always the best option. It requires
allocating extra main memory and it is often ineﬃcient. The chapter gives examples of when
recursion should be applied and when alternative approaches perform better. The chapter
shows many examples of recursive programs. These include the famous Tower of Hanoi
game, binary search, and popular sorting algorithms.
14.1 Base Case and General Case
In a land far far way, there lived a king that liked to play chess. He was also single
and wanted to ﬁnd his queen. One day, a peasant approached the king and made him the
following proposal. They would play a game of chess. If the king won, then he could marry
the peasant’s daughter, who happened to be the fairest of them all. However, if the peasant
won, then the king had to give him some grain. The peasant asked for one grain of wheat
for the ﬁrst day and one grain of wheat on the second day. For each day after, the peasant
requested to be given the total of the previous two days. Since there are 64 squares on the
chessboard, the peasant suggested that he receive grain for “only” 64 days. Before agreeing
to the deal, the king decided to write a short program that calculated how many grains of
wheat he may need to part with in the unlikely event that he lost the chess match. Here is
the program that he wrote.
319

Get Learning Java Through Games now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.