Java Reference
In-Depth Information
Summary of Key Concepts
Recursion is a programming technique in which a method calls itself. A
key to being able to program recursively is to be able to think recursively.
■
Any recursive definition must have a non-recursive part, called the base
case, which permits the recursion to eventually end.
■
Mathematical problems and formulas are often expressed recursively.
■
Each recursive call to a method creates new local variables and
parameters.
■
A careful trace of recursive processing can provide insight into the way it
is used to solve a problem.
■
Recursion is the most elegant and appropriate way to solve some
problems, but for others it is less intuitive than an iterative solution.
■
The Towers of Hanoi solution has exponential complexity, which is very
inefficient. Yet the implementation of the solution is incredibly short and
elegant.
■
A fractal is a geometric shape that is defined naturally in a recursive manner.
■
Exercises
Visit
www.myprogramminglab.com
to complete many of these Exercises
online and get instant feedback.
EX 12.1 Write a recursive definition of a valid Java identifier (see
Chapter 1).
EX 12.2 Write a recursive definition of
x
y (
x
raised to the power
y
),
where
x
and
y
are integers and
y
> 0.
EX 12.3 Write a recursive definition of
i
*
j
(integer multiplication),
where
i
> 0. Define the multiplication process in terms of integer
addition. For example, 4 * 7 is equal to 7 added to itself 4 times.
EX 12.4 Write a recursive definition of the Fibonacci numbers. The
Fibonacci numbers are a sequence of integers, each of which is
the sum of the previous two numbers. The first two numbers in
the sequence are 0 and 1. Explain why you would not normally
use recursion to solve this problem.
Search WWH ::
Custom Search