## Description

This lab assignment will give you practice with simple recursive functions.

Getting Started

Visit Piazza and download the “bare bones” file lab7.py onto your computer. Open lab7.py in PyCharm and

fill in the following information at the top:

1. your first and last name as they appear in Blackboard

2. your Net ID (e.g., jsmith)

3. your Stony Brook ID # (e.g., 111999999)

4. the course number (CSE 101)

5. the assignment name and number (Lab #7)

Submit your final lab7.py file to Blackboard by the due date and time. Late work will not be graded. Code that

crashes and cannot be graded will earn no credit.

Part I: Recursive Hailstone Sequence (20 points)

Recall the hailstone sequence from an earlier assignment: the integer sequence that results from manipulating a

positive integer value n as follows:

• If n is even, divide it by 2 (using integer division)

• If n is odd, multiply it by 3 and then add 1

Repeat this process until you reach 1.

For example, starting with n = 5, we get the sequence 5, 16, 8, 4, 2, 1.

If n = 6, we get the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1.

Complete the function rec hailstone length(n), which recursively computes and then returns the length

of the hailstone sequence starting with n.

One possible recursive algorithm you can consider implementing is this:

CSE 101 – Spring 2018 Lab #7 Page 1

if n = 1 then

return 1

otherwise

if n is even

return 1 + the next hailstone value according to the “even” formula

else

return 1 + the next hailstone value according to the “odd” formula

Note: Non-recursive solutions to the problem that use loops will not earn credit.

Examples:

Function Call Return Value

rec hailstone length(2596) 147

rec hailstone length(641) 52

rec hailstone length(3153) 62

rec hailstone length(3148) 62

rec hailstone length(3012) 23

rec hailstone length(779) 60

rec hailstone length(308) 25

rec hailstone length(3722) 39

rec hailstone length(3448) 44

rec hailstone length(1171) 58

Part II: Recursive Work Order Calculator (20 points)

Write a recursive function rec work cost() that takes two arguments, in this order:

1. work orders: a list of strings representing work orders

2. hourly costs: a tuple of three integers representing the costs per hour to fix a pipe, window and sprinkler, respectively

Each work order in work orders starts with a single digit and is followed by ’pipe’, ’window’ or ’sprinkler’.

The digit indicates the number of hours that will be spent repairing the given item. For instance, ’5sprinkler’

indicates that it will take 5 hours to repair a particular sprinkler. For the moment, assuming that hourly costs

= (6, 2, 9). This means that it will cost 5 × $9 = $45 to repair the sprinkler. In general, hourly costs

will contain a different trio of values.

The function recursively processes the entire list of work orders and returns the total cost of performing all the

work orders.

One possible recursive algorithm you can consider implementing is this:

if work_orders is empty then

return 0

otherwise

let remaining_costs be the cost of completing all of the other work orders

CSE 101 – Spring 2018 Lab #7 Page 2

(i.e., work_orders[1] and all later work orders)

if work_orders[0] is for a pipe then

return (the cost to repair the pipe + remaining_costs)

otherwise, if work_orders[0] is for a window then

return (the cost to repair the window + remaining_costs)

otherwise, work_orders[0] must be for a sprinkler, so

return (the cost to repair the sprinkler + remaining_costs)

Note: Non-recursive solutions to the problem that use loops will not earn credit.

Examples:

Function Call Return Value

rec work cost([’1sprinkler’, ’4window’, ’3pipe’, ’1window’,

’4pipe’, ’3pipe’, ’2window’], (7, 4, 6))

104

rec work cost([’3pipe’, ’3sprinkler’, ’4pipe’, ’3pipe’,

’1pipe’, ’3window’, ’2sprinkler’, ’4sprinkler’, ’3pipe’,

’4window’], (3, 6, 6))

138

rec work cost([’2pipe’, ’4pipe’, ’4pipe’, ’3sprinkler’,

’4window’, ’1sprinkler’], (6, 4, 5))

96

rec work cost([’3window’, ’4window’, ’1sprinkler’, ’4window’,

’2pipe’], (7, 4, 8))

66

rec work cost([’4window’, ’3window’, ’2pipe’, ’2sprinkler’,

’3sprinkler’, ’2pipe’], (8, 6, 4))

94

rec work cost([’1window’, ’3pipe’, ’3window’, ’3window’,

’3sprinkler’, ’2sprinkler’], (7, 7, 7)]

105

rec work cost([’2sprinkler’, ’2window’, ’3sprinkler’, ’2pipe’,

’4sprinkler’, ’2sprinkler’], (3, 5, 3))

49

rec work cost([’4window’, ’3sprinkler’, ’2pipe’, ’2pipe’,

’3window’, ’2window’, ’4sprinkler’, ’1window’, ’2sprinkler’,

’1pipe’], (7, 2, 7))

118

rec work cost([’3sprinkler’, ’2sprinkler’, ’2pipe’, ’1pipe’,

’1pipe’, ’2pipe’, ’1pipe’, ’4pipe’, ’1pipe’, ’3sprinkler’],

(2, 3, 5))

64

rec work cost([’4pipe’, ’4sprinkler’, ’4sprinkler’, ’3window’,

’4pipe’, ’4pipe’, ’3pipe’, ’1window’, ’4pipe’, ’2window’], (3,

7, 7))

155

How to Submit Your Work for Grading

To submit your .py file for grading:

1. Login to Blackboard and locate the course account for CSE 101.

2. Click on “Assignments” in the left-hand menu and find the link for this assignment.

3. Click on the link for this assignment.

4. Click the “Browse My Computer” button and locate the .py file you wish to submit. Submit only that one

CSE 101 – Spring 2018 Lab #7 Page 3

.py file.

5. Click the “Submit” button to submit your work for grading.

Oops, I messed up and I need to resubmit a file!

No worries! Just follow the above directions again. We will grade only your last submission.

CSE 101 – Spring 2018 Lab #7 Page 4