程序代写代做代考 algorithm c++ data structure PowerPoint Presentation

PowerPoint Presentation

Recursion: The Mirrors
Chapter 2

Contents
Recursive Solutions
Recursion That Returns a Value
Recursion That Performs an Action
Recursion with Arrays
Organizing Data
More Examples
Recursion and Efficiency

Recursive Solutions
Recursion breaks a problem into smaller identical problems
Some recursive solutions are inefficient, impractical
Complex problems can have simple recursive solutions

Recursive Solutions
FIGURE 2-1 A recursive solution
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Recursive Solutions
A recursive solution calls itself
Each recursive call solves an identical, smaller problem
Test for base case enables recursive calls to stop
Eventually one of smaller calls will be base case

A Recursive Valued Function
The factorial of n
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Valued Function
FIGURE 2-2 fact(3)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Box Trace
FIGURE 2-3 A box
FIGURE 2-4 The beginning of the box trace
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Box Trace
FIGURE 2-5 Box trace of fact(3)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Box Trace
FIGURE 2-5 Box trace of fact(3) … continued
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-6 A recursive solution
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The function writeBackwards

A Recursive Void Function
FIGURE 2-7 Box trace of writeBackward(“cat”)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-7 writeBackward(“cat”)continued
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-7 writeBackward(“cat”)continued
Data Structures and Problem Solving with C++: Walls and Mirrors, Frank Carrano, © 2012

A Recursive Void Function
FIGURE 2-8 Box trace of writeBackward(“cat”)
in pseudocode
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-8 Box trace of writeBackward(“cat”)
in pseudocode (continued)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013`

A Recursive Void Function
FIGURE 2-8 Box trace of writeBackward(“cat”)
in pseudocode (continued)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-8 Box trace of writeBackward(“cat”)
in pseudocode (concluded)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-9 Box trace of writeBackward2(“cat”)
in pseudocode
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-9 Box trace of writeBackward2(“cat”)
in pseudocode (continued)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

A Recursive Void Function
FIGURE 2-9 Box trace of writeBackward2(“cat”)
in pseudocode (concluded)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Writing an Array’s Entries in Backward Order
Pseudocode

Writing an Array’s Entries in Backward Order
Source code

The Binary Search
A high-level binary search for the array problem

The Binary Search
Issues to consider
How to pass a half array to recursive call
How to determine which half of array has target value
What is the base case?
How will result of binary search be indicated?
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Binary Search
FIGURE 2-10 Box traces of binarySearch with
anArray = <1, 5, 9, 12, 15, 21, 29, 31>:
(a) a successful search for 9
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Binary Search
FIGURE 2-10 Box traces of binarySearch with
anArray = <1, 5, 9, 12, 15, 21, 29, 31>:
(b) an unsuccessful search for 6
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Binary Search
FIGURE 2-11 Box trace with a reference argument
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Finding the Largest Value
in an Array
Recursive algorithm

Finding the Largest Value
in an Array
FIGURE 2-12 Recursive solution to the
largest-value problem
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Finding the Largest Value
in an Array
FIGURE 2-13 The recursive calls that maxArray(<1,6,8,3>) generates
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Finding the kth Smallest
Value of an Array
FIGURE 2-14 A sample array
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The recursive solution proceeds by:
Selecting a pivot value in array
Cleverly arranging/partitioning, values in array about this pivot value
Recursively applying strategy to one of partitions

Finding the kth Smallest
Value of an Array
FIGURE 2-15 A partition about a pivot
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Finding the kth Smallest
Value of an Array
High level pseudocode solution:
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Organizing Data
Towers of Hanoi
FIGURE 2-16 (a) The initial state;
(b) move n – 1 disks from A to C;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Towers of Hanoi
FIGURE 2-16 (c) move 1 disk from A to B;
(d) move n – 1 disks from C to B
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Towers of Hanoi
Pseudocode solution:
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Towers of Hanoi
FIGURE 2-17 The order of recursive calls that results from solve Towers(3, A, B, C)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Towers of Hanoi
Source code for solveTowers

The Fibonacci Sequence
(Multiplying Rabbits)
Assumed “facts” about rabbits:
Rabbits never die.
A rabbit reaches sexual maturity exactly two months after birth
Rabbits always born in male-female pairs.
At the beginning of every month, each sexually mature male-female pair gives birth to exactly one male-female pair.

The Fibonacci Sequence
(Multiplying Rabbits)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Month Rabbit Population
1 One pair
2 One pair, still
3 Two pairs
4 Three pairs
5 Five pairs
6 8 pairs

The Fibonacci Sequence
(Multiplying Rabbits)
FIGURE 2-18 Recursive solution to the rabbit problem
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Fibonacci Sequence
(Multiplying Rabbits)
A C++ function to compute rabbit(n)

The Fibonacci Sequence
(Multiplying Rabbits)
FIGURE 2-19 The recursive calls that rabbit(7) generates
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Choosing k Out of n Things
Recursive solution:

Choosing k Out of n Things
Recursive function:

Choosing k Out of n Things
FIGURE 2-20 The recursive calls
that g (4, 2) generates
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Recursion and Efficiency
Inefficiency factors

Overhead associated with function calls
Inherent inefficiency of some recursive algorithms
Principle:

Do not use recursive solution if inefficient and clear, efficient iterative solution exists
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

End
Chapter 2

Related Posts