35
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
void ricochet(Car& moving_car);
The recursive call
36
At last! The recursive call has finished its work, solving the smaller
problem. In the solution of the smaller problem, the recursive call
Another key point: You don’t need to know all the details of how that
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
void ricochet(Car& moving_car);
The recursive call
99 ft.
37
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
the barrier. In this case, just turn the car around.
void ricochet(Car& moving_car);
What is the last step
that’s needed to return
38
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
void ricochet(Car& moving_car);
What is the last step
39
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
the barrier. In this case, just turn the car around.
void ricochet(Car& moving_car);
40
Question: What do you suppose would happen if we forgot to include a
base case?
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
the barrier. In this case, just turn the car around.
void ricochet(Car& moving_car);
This is the base case.
41
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
the barrier. In this case, just turn the car around.
❷Otherwise, the car has not yet reached the barrier, so
start with:
void ricochet(Car& moving_car);
When the problem is
42
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
void ricochet(Car& moving_car);
43
Generally a bit of extra work is done before the recursive call, in order
Pseudocode for ricochet
❶if moving_car.is_blocked( ), then the car is already at
the barrier. In this case, just turn the car around.
❷Otherwise, the car has not yet reached the barrier, so
void ricochet(Car& moving_car);
problem..
44
Implementation of ricochet
void ricochet(Car& moving_car)
{
if (moving_car.is_blocked( ))
45
An Exercise
Can you write ricochet as a
new member function of the
46
Two key points:
1. The recursive member function does not need a parameter, since it
must be activated by a particular car. For example, if you have a car
named racer, then you can activate racer’s ricochet function with:
2. The recursive member function activates itself. Do you see where
this happens?
An Exercise
void Car::ricochet( )
{
if (is_blocked( ))
turn_around( ); // Base case
One solution:
47
Presentation copyright 1997 Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright