Recursion - Data Structures and Problem Solving Using Java - page 293

chapter 7

recursion

A method that is partially defined in terms of itself is called recursive .
Like many languages, Java supports recursive methods. Recursion, which is
the use of recursive methods, is a powerful programming tool that in many
cases can yield both short and efficient algorithms. In this chapter we explore
how recursion works, thus providing some insight into its variations, limita-
tions, and uses. We begin our discussion of recursion by examining the math-
ematical principle on which it is based: mathematical induction . Then we give
examples of simple recursive methods and prove that they generate correct
answers.
In this chapter, we show

The four basic rules of recursion

n

Numerical applications of recursion, leading to implementation of an
encryption algorithm

n

A general technique called divide and conquer

n

A general technique called dynamic programming, which is similar to
recursion but uses tables instead of recursive method calls

n

A general technique called backtracking, which amounts to a careful
exhaustive search

n