Java Reference
In-Depth Information
Chapter 5
Recursion
In this chapter, we will explain the following:
•
What a recursive definition is
•
How to write recursive functions in Java
•
How to convert from decimal to binary
•
How to print a linked list in reverse order
•
How to solve Towers of Hanoi
•
How to write an efficient power function
•
How to sort using merge sort
•
How to use recursion to keep track of pending subproblems
•
How to implement backtracking using recursion by finding a path through a maze
5.1 Recursive Definition
A
recursive definition
is one that is defined in terms of itself. Perhaps the most common example is the
factorial
function. The factorial of a non-negative integer,
n
(written as
n
!), is defined as follows:
0! = 1
n
! =
n
(
n
- 1)!,
n
> 0
Here,
n
! is defined in terms of (
n
- 1)!, but what is (
n
- 1)! exactly? To find out, we must apply the definition of
factorial! In this case, we have this:
(
n
- 1)! = 1, if (
n
- 1) = 0
(
n
- 1)! = (
n
- 1)(
n
- 2)! if (
n
- 1) > 0
What is 3! now?
•
Since 3 > 0, it is 3×2!.
•
Since 2 > 0, 2! is 2×1!, and 3! becomes 3×2×1!.
•
Since 1 > 0, 1! is 1×0!, and 3! becomes 3×2×1×0!.Since 0! is 1, we have 3! = 3×2×1×1 = 6.
Loosely, we say that
n
! is the product of all integers from 1 to
n
.
Search WWH ::
Custom Search