Java Reference
In-Depth Information
Chapter
7
Recursion
Contents
What Is Recursion?
Tracing a Recursive Method
Recursive Methods That Return a Value
Recursively Processing an Array
Recursively Processing a Linked Chain
The Time Efficiency of Recursive Methods
The Time Efficiency of
countDown
The Time Efficiency of Computing
x
n
A Simple Solution to a Difficult Problem
A Poor Solution to a Simple Problem
Tail Recursion
Indirect Recursion
Using a Stack Instead of Recursion
Prerequisites
Appendix B Java Classes
Chapter 2 Bag Implementations That Use Arrays
Chapter 3 A Bag Implementation That Links Data
Chapter 4 The Efficiency of Algorithms
Chapter 5 Stacks
Objectives
After studying this chapter, you should be able to
•
Decide whether a given recursive method will end successfully in a finite amount of time
•
Write a recursive method
•
Estimate the time efficiency of a recursive method
•
Identify tail recursion and replace it with iteration