Learning Java Through Games

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

infinitely 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 inefficient. 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 find 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 first 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