Slides 11

Chapter 11: Recursion
Presentation slides for
Java Software Solutions

Foundations of Program Design
Third Edition
Presented by
Ali Kassem
Java Software Solutions is published by Addison-Wesley
Presentation slides are copyright 2002 by John Lewis and William Loftus. All rights reserved.
Instructors using the textbook may use and modify these slides for pedagogical purposes.
Recursion
 Recursion is a fundamental programming technique that
can provide elegant solutions certain kinds of problems
 Chapter 11 focuses on:

• thinking in a recursive manner
• programming in a recursive manner
• the correct use of recursion
• examples using recursion
• recursion in graphics
Ali Kassem 2
Recursive Thinking
 Recursion is a programming technique in which a method
can call itself to solve a problem
 A recursive definition is one which uses the word or concept

being defined in the definition itself; when defining an
English word, a recursive definition usually is not helpful
 But in other situations, a recursive definition can be an

appropriate way to express a concept
 Before applying recursion to programming, it is best to

practice thinking recursively
Ali Kassem 3
Recursive Definitions
 Consider the following list of numbers:
24, 88, 40, 37
 A list can be defined recursively
A LIST is a: number
or a: number comma LIST
 That is, a LIST is defined to be a single number, or a

number followed by a comma followed by a LIST
 The concept of a LIST is used to define itself
Ali Kassem 4
 The recursive part of the LIST definition is used several
times, ultimately terminating with the non-recursive part:
number comma LIST

24 , 88, 40, 37
number comma LIST

88 , 40, 37
number comma LIST

40 , 37
number
37
Ali Kassem 5
Infinite Recursion
 All recursive definitions must have a non-recursive part
 If they don't, there is no way to terminate the recursive

path
 A definition without a non-recursive part causes infinite

recursion
 This problem is similar to an infinite loop with the

definition itself causing the infinite “loop”
 The non-recursive part often is called the base case
Ali Kassem 6
 Mathematical formulas often are expressed recursively
 N!, for any positive integer N, is defined to be the product

of all integers between 1 and N inclusive
 This definition can be expressed recursively as:
1! = 1
N! = N * (N-1)!
 The concept of the factorial is defined in terms of another

factorial until the base case of 1! is reached
Ali Kassem 7
120
5!
24
5 * 4!
4 * 3! 6
3 * 2!
2
2 * 1!
1
Ali Kassem 8
Recursive Programming
 A method in Java can invoke itself; if set up that way, it is
called a recursive method
 The code of a recursive method must be structured to

handle both the base case and the recursive case
 Each call to the method sets up a new execution

environment, with new parameters and new local variables
 As always, when the method execution completes, control

returns to the method that invoked it (which may be an
earlier invocation of itself)
Ali Kassem 9
 Consider the problem of computing the sum of all the
numbers between 1 and any positive integer N, inclusive
 This problem can be expressed recursively as:
N N-1 N-2
= N + = N + (N-1) +
i=1 i=1 i=1
= etc.
Ali Kassem 10
public int sum (int num)

{
int result;
if (num == 1)
result = 1;
else
result = num + sum (num - 1);
return result;
}
result = 6
main
sum(3)
result = 3
sum
sum(2)
result = 1
sum
sum(1)
sum
Ali Kassem 12
Recursion vs. Iteration
 Just because we can use recursion to solve a problem,
doesn't mean we should
 For instance, we usually would not use recursion to solve

the sum of 1 to N problem, because the iterative version is
easier to understand; in fact, there is a formula which is
superior to both recursion and iteration!
 You must be able to determine when recursion is the

correct technique to use
Ali Kassem 13
Recursion vs. Iteration
 Every recursive solution has a corresponding iterative
solution
 For example, the sum (or the product) of the numbers

between 1 and any positive integer N can be calculated with
a for loop
 Recursion has the overhead of multiple method invocations
 Nevertheless, recursive solutions often are more simple and

elegant than iterative solutions
Indirect Recursion
 A method invoking itself is considered to be direct recursion
 A method could invoke another method, which invokes

another, etc., until eventually the original method is invoked
again
 For example, method m1 could invoke m2, which invokes

m3, which in turn invokes m1 again until a base case is
reached
 This is called indirect recursion, and requires all the same

care as direct recursion
 It is often more difficult to trace and debug

Ali Kassem 15
Indirect Recursion
m1 m2 m3
m1 m2 m3
m1 m2 m3
Ali Kassem 16
Maze Traversal
 We can use recursion to find a path through a maze; a path
can be found from any location if a path can be found from
any of the location’s neighboring locations
 At each location we encounter, we mark the location as

“visited” and we attempt to find a path from that location’s
“unvisited” neighbors
 Recursion keeps track of the path through the maze
 The base cases are an prohibited move or arrival at the

final destination
Maze Traversal
 See MazeSearch.java (page xxx)

 See Maze.java (page xxx)
MazeSearch.java
Maze.java
Towers of Hanoi
 The Towers of Hanoi is a puzzle made up of three vertical
pegs and several disks that slide on the pegs
 The disks are of varying size, initially placed on one peg

with the largest disk on the bottom with increasingly
smaller disks on top
 The goal is to move all of the disks from one peg to another
according to the following rules:
• We can move only one disk at a time
• We cannot place a larger disk on top of a smaller disk
• All disks must be on some peg except for the disk in transit between
pegs
Towers of Hanoi
 (Figure 11.5 here)
Towers of Hanoi
 A solution to the three-disk Towers of Hanoi puzzle

Towers of Hanoi
 To move a stack of N disks from the original peg to the
destination peg
• move the topmost N - 1 disks from the original peg to the extra peg
• move the largest disk from the original peg to the destination peg
• move the N-1 disks from the extra peg to the destination peg
• The base case occurs when a “stack” consists of only one disk
 This recursive solution is simple and elegant even though the

number of move increases exponentially as the number of
disks increases
 The iterative solution to the Towers of Hanoi is much more

complex
Towers of Hanoi
 See SolveTowers.java (page xxx)

 See TowersOfHanoi.java (page xxx)
SolveTowers.java
TowersOfHanoi.java
Recursion in Graphics
 Consider the task of repeatedly displaying a set of tiled
images in a mosaic in which one of the tiles contains a copy
of the entire collage
 The base case is reached when the area for the “remaining”
tile shrinks to a certain size
 See TiledPictures.java (page xxx)
Ali Kassem 28
TiledPictures.java
Fractals
 A fractal is a geometric shape than can consist of the same
pattern repeated in different scales and orientations
 The Koch Snowflake is a particular fractal that begins with

an equilateral triangle
 To get a higher order of the fractal, the middle of each edge

is replaced with two angled line segments
Fractals
 See KochSnowflake.java (page xxx)

 See KochPanel.java (page xxx)
KochSnowflake.java
KochPanel.java
Summary
 Chapter 11 has focused on:
• thinking in a recursive manner
• programming in a recursive manner
• the correct use of recursion
• examples using recursion
• recursion in graphics

Slides 11

Uploaded by

Copyright:

Available Formats

Slides 11

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Slides 11

Uploaded by

Copyright:

Available Formats

Chapter 11: Recursion

Presentation slides for

Java Software Solutions

Java Software Solutions is published by Addison-Wesley

 Chapter 11 focuses on:

 A recursive definition is one which uses the word or concept

 But in other situations, a recursive definition can be an

 Before applying recursion to programming, it is best to

24, 88, 40, 37

 A list can be defined recursively

 That is, a LIST is defined to be a single number, or a

 The concept of a LIST is used to define itself

number comma LIST

number comma LIST

number comma LIST

 If they don't, there is no way to terminate the recursive

 A definition without a non-recursive part causes infinite

 This problem is similar to an infinite loop with the

 The non-recursive part often is called the base case

 N!, for any positive integer N, is defined to be the product

 This definition can be expressed recursively as:

 The concept of the factorial is defined in terms of another

 The code of a recursive method must be structured to

 Each call to the method sets up a new execution

 As always, when the method execution completes, control

 This problem can be expressed recursively as:

public int sum (int num)

 For instance, we usually would not use recursion to solve

 You must be able to determine when recursion is the

 For example, the sum (or the product) of the numbers

 Recursion has the overhead of multiple method invocations

 Nevertheless, recursive solutions often are more simple and

 A method could invoke another method, which invokes

 For example, method m1 could invoke m2, which invokes

 This is called indirect recursion, and requires all the same

 It is often more difficult to trace and debug

 At each location we encounter, we mark the location as

 Recursion keeps track of the path through the maze

 The base cases are an prohibited move or arrival at the

 See MazeSearch.java (page xxx)

 The disks are of varying size, initially placed on one peg

 (Figure 11.6 here)

 This recursive solution is simple and elegant even though the

 The iterative solution to the Towers of Hanoi is much more

 See SolveTowers.java (page xxx)

 See TiledPictures.java (page xxx)

 The Koch Snowflake is a particular fractal that begins with

 To get a higher order of the fractal, the middle of each edge

 See KochSnowflake.java (page xxx)

You might also like