Transcript Chapter 11-12: Recursion/Data Structures

CISH 4960 Introduction to Programming
Introduction to Programming
CISH 4960
Fall 2002
•Lecture 10
Recursion/Data Structures
•Tom Blough
[email protected]
www.rh.edu/~blought/cish4960
860.618.4148
Lecture 10
1
CISH 4960 Introduction to Programming
Recursion
• Recursion is a fundamental programming
technique that can provide an elegant solution
certain kinds of problems
• Chapter 11 focuses on:
–
–
–
–
Lecture 10
thinking in a recursive manner
programming in a recursive manner
the correct use of recursion
recursion examples
2
CISH 4960 Introduction to Programming
Recursive Thinking
• 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 is often 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
Lecture 10
3
CISH 4960 Introduction to Programming
Recursive Definitions
• Consider the following list of numbers:
24, 88, 40, 37
• Such a list can be defined as
A LIST is a:
or a:
number
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
Lecture 10
4
CISH 4960 Introduction to Programming
Recursive Definitions
• The recursive part of the LIST definition is
used several times, terminating with the nonrecursive part:
number comma LIST
24
,
88, 40, 37
number comma LIST
88
,
40, 37
number comma LIST
40
,
37
number
37
Lecture 10
5
CISH 4960 Introduction to Programming
Infinite Recursion
• All recursive definitions have to have a nonrecursive part
• If they didn't, there would be no way to
terminate the recursive path
• Such a definition would cause infinite recursion
• This problem is similar to an infinite loop, but
the non-terminating "loop" is part of the
definition itself
• The non-recursive part is often called the base
case
Lecture 10
6
CISH 4960 Introduction to Programming
Recursive Definitions
• 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!
N!
=
=
1
N * (N-1)!
• The concept of the factorial is defined in terms
of another factorial
• Eventually, the base case of 1! is reached
Lecture 10
7
CISH 4960 Introduction to Programming
Recursive Definitions
5!
120
5 * 4!
24
4 * 3!
6
3 * 2!
2
2 * 1!
1
1
Lecture 10
8
CISH 4960 Introduction to Programming
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 local
variables
• As always, when the method completes, control
returns to the method that invoked it (which
may be an earlier invocation of itself)
Lecture 10
9
CISH 4960 Introduction to Programming
Recursive Programming
• Consider the problem of computing the sum of all
the numbers between 1 and any positive integer N
• This problem can be recursively defined as:
N
N-1
=
N
i=1
=
Lecture 10
+
N-2
=
i=1
N + (N-1) +
i=1
etc.
10
CISH 4960 Introduction to Programming
Recursive Programming
result = 6
main
sum(3)
sum
result = 3
sum(2)
sum
result = 1
sum(1)
sum
Lecture 10
11
CISH 4960 Introduction to Programming
Recursive Programming
• Note that 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
• However, for some problems, recursion
provides an elegant solution, often cleaner than
an iterative version
• You must carefully decide whether recursion is
the correct technique for any problem
Lecture 10
12
CISH 4960 Introduction to Programming
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
• This is called indirect recursion, and requires
all the same care as direct recursion
• It is often more difficult to trace and debug
Lecture 10
13
CISH 4960 Introduction to Programming
Indirect Recursion
m1
m2
m3
m1
m2
m1
Lecture 10
m3
m2
m3
14
CISH 4960 Introduction to Programming
Maze Traversal
• We can use recursion to find a path through a
maze
• From each location, we can search in each
direction
• Recursion keeps track of the path through the
maze
• The base case is an invalid move or reaching
the final destination
• See MazeSearch.java (page 611)
• See Maze.java (page 612)
Lecture 10
15
CISH 4960 Introduction to Programming
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 ones on top
• The goal is to move all of the disks from one
peg to another under the following rules:
– We can move only one disk at a time
– We cannot move a larger disk on top of a smaller one
Lecture 10
16
CISH 4960 Introduction to Programming
Towers of Hanoi
• An iterative solution to the Towers of Hanoi
is quite complex
• A recursive solution is much shorter and
more elegant
• See SolveTowers.java (page 618)
• See TowersOfHanoi.java (page 619)
Lecture 10
17
CISH 4960 Introduction to Programming
Data Structures
• We can now explore some advanced
techniques for organizing and managing
information
• Chapter 12 focuses on:
–
–
–
–
–
Lecture 10
dynamic structures
Abstract Data Types (ADTs)
linked lists
queues
stacks
18
CISH 4960 Introduction to Programming
Static vs. Dynamic Structures
• A static data structure has a fixed size
• This meaning is different than those associated
with the static modifier
• Arrays are static; once you define the number
of elements it can hold, it doesn’t change
• A dynamic data structure grows and shrinks as
required by the information it contains
Lecture 10
19
CISH 4960 Introduction to Programming
Object References
• Recall that an object reference is a variable
that stores the address of an object
• A reference can also be called a pointer
• They are often depicted graphically:
student
John Smith
40725
3.57
Lecture 10
20
CISH 4960 Introduction to Programming
References as Links
• Object references can be used to create
links between objects
• Suppose a Student class contained a
reference to another Student object
John Smith
40725
3.57
Lecture 10
Jane Jones
58821
3.72
21
CISH 4960 Introduction to Programming
References as Links
• References can be used to create a
variety of linked structures, such as a
linked list:
studentList
Lecture 10
22
CISH 4960 Introduction to Programming
Abstract Data Types
• An abstract data type (ADT) is an organized
collection of information and a set of operations
used to manage that information
• The set of operations define the interface to the
ADT
• As long as the ADT accurately fulfills the
promises of the interface, it doesn't really
matter how the ADT is implemented
• Objects are a perfect programming mechanism
to create ADTs because their internal details are
encapsulated
Lecture 10
23
CISH 4960 Introduction to Programming
Abstraction
• Our data structures should be abstractions
• That is, they should hide details as appropriate
• We want to separate the interface of the
structure from its underlying implementation
• This helps manage complexity and makes the
structures more useful
Lecture 10
24
CISH 4960 Introduction to Programming
Intermediate Nodes
• The objects being stored should not have to
deal with the details of the data structure in
which they may be stored
• For example, the Student class stored a link
to the next Student object in the list
• Instead, we can use a separate node class that
holds a reference to the stored object and a link
to the next node in the list
• Therefore the internal representation actually
becomes a linked list of nodes
Lecture 10
25
CISH 4960 Introduction to Programming
Book Collection
• Let’s explore an example of a collection of Book
objects
• The collection is managed by the BookList class,
which has an private inner class called BookNode
• Because the BookNode is private to BookList,
the BookList methods can directly access
BookNode data without violating encapsulation
• See MagazineRack.java (page 641)
• See MagazineList.java (page 642)
• See Magazine.java (page 644)
Lecture 10
26
CISH 4960 Introduction to Programming
Other Dynamic List
Implementations
• It may be convenient to implement as list
as a doubly linked list, with next and
previous references:
list
Lecture 10
27
CISH 4960 Introduction to Programming
Other Dynamic List Implementations
• It may also be convenient to use a separate
header node, with references to both the front and
rear of the list
list
Lecture 10
count: 4
front
rear
28
CISH 4960 Introduction to Programming
Queues
• A queue is similar to a list but adds items
only to the end of the list and removes
them from the front
• It is called a FIFO data structure: FirstIn, First-Out
• Analogy: a line of people at a bank
teller’s window
enqueue
Lecture 10
dequeue
29
CISH 4960 Introduction to Programming
Queues
• We can define the operations on a queue as follows:
– enqueue - add an item to the rear of the queue
– dequeue - remove an item from the front of the queue
– getFront – return the object at the front of the queue, but
do not remove it from the queue
– isEmpty - returns true if the queue is empty
– clear – removes all items from the queue
• As with our linked list example, by storing generic Object
references, any object can be stored in the queue
• Queues are often helpful in simulations and any processing in
which items get “backed up”
Lecture 10
30
CISH 4960 Introduction to Programming
Side Effects in Functions
• Note the Queue ADT had dequeue and getFront
• Methods can be divided into two types
– Commands – modify objects
– Queries – return information about objects
• Queries that change objects are said to have “side
effects”
• There are mathematical reasons for not allowing side
effects in programming – referential transparency
• In layman’s terms – “Asking a question should not
change the answer”
• getFront can be called repeatedly and return the same
result each time until a command method is called
Lecture 10
31
CISH 4960 Introduction to Programming
Stacks
• A stack ADT is also linear, like a list or
queue
• Items are added and removed from only
one end of a stack
• It is therefore LIFO: Last-In, First-Out
• Analogy: a stack of plates
Lecture 10
32
CISH 4960 Introduction to Programming
Stacks
• Stacks are often drawn vertically:
push
Lecture 10
pop
33
CISH 4960 Introduction to Programming
Stacks
• Some stack operations:
–
–
–
–
–
push - add an item to the top of the stack
pop - remove an item from the top of the stack
getTop - retrieves the top item without removing it
isEmpty - returns true if the stack is empty
clear – removes all items from the stack
• The java.util package contains a Stack
class, which is implemented using a Vector
• See Decode.java (page 649)
Lecture 10
34
CISH 4960 Introduction to Programming
Trees vs. Linked List
• Linked list -- collection of nodes where each
node references only one neighbor
• Tree -- also collection of nodes, but each node
may reference multiple neighbors
Lecture 10
35
CISH 4960 Introduction to Programming
Trees
• Trees can be used to model hierarchical
organization of data
Lecture 10
36
CISH 4960 Introduction to Programming
•
•
•
•
•
•
•
•
•
Trees
A is the root node
B is the parent of D and E
D and E are children of B
(C \ F) is an edge
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 are external nodes, or leaves (i.e., nodes with
no children)
A, B, C, D, E, F, G, H, I are internal nodes
depth (level) of E is 2 (number of edges to root)
height of the tree is 3 (max number of edges)
degree of node B is 2 (number of children)
Lecture 10
37
CISH 4960 Introduction to Programming
Graph definitions
There are two kinds of graphs: directed graphs (sometimes
called digraphs) and undirected graphs
start
fill pan
with water
add salt
to water
Birmingham
take egg
from fridge
break egg
into pan
boil
water
A directed graph
Lecture 10
60
Rugby
150
190
140
100
London
190
Bristol
110
Cambridge
120
Dover
Southhampton
An undirected graph
38
CISH 4960 Introduction to Programming
Graph Terminology
• A graph is a collection of nodes (or vertices) and edges (or
arcs)
– Each node contains an element
– Each edge connects two nodes together (or possibly the same node
to itself) and may contain an edge attribute
• A directed graph is one in which the edges have a direction
• An undirected graph is one in which the edges do not have
a direction
– Note: Whether a graph is directed or undirected is a logical
distinction—it describes how we think about the graph
– Depending on the implementation, we may or may not be able to
follow a directed edge in the “backwards” direction
Lecture 10
39
CISH 4960 Introduction to Programming
Collection Classes
• The Java 2 platform contains a Collections API
• This group of classes represent various data
structures used to store and manage objects
• Their underlying implementation is implied in
the class names, such as ArrayList and
LinkedList
• Several interfaces are used to define operations
on the collections, such as List, Set,
SortedSet, Map, and SortedMap
Lecture 10
40
CISH 4960 Introduction to Programming
Recursion Example
0
1/2
1/4
1/8
1/16
3/16
Lecture 10
3/8
5/16
7/16
1
3/4
5/8
9/16
11/16
7/8
13/16
15/16
41
CISH 4960 Introduction to Programming
Data Structure Example
Front
Queue
Back
• Queue Interface:
– void enqueue( object obj)
– void dequeue()
– object getFront()
– boolean isEmpty()
– void clear()
Lecture 10
42