O'Reilly logo

Learning Java Through Games by Lubomir Stanchev

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required