Worth: 10 points (5 pts per problem)

Objective: To let you practice recursion!

Collaboration: You may work together, but everyone should turn in his/her own copy of code. Late assignments will be docked 3 points per 24 hour period.

What to turn in: A print out of your code

Recursion is defining something in terms of itself. For example, consider "factorial." 5! = 1*2*3*4*5. This is an iterative definition. You could write a loop which accomplishes this. A recursive definition is 5! = 5*4!, where 4! = 4*3! … In this case, your base case is 0! = 1 (by definition).

I am assuming most of you are familiar with recursion. If you need a refresher, read section 1.3 in your data structures book. If you need more of a refresher, please come see me.

1a. Write a program that computes xⁿ iteratively.

b. Write a program that computes xⁿ recursively.

2a. Suppose I need 9 hours of sleep per night (oh, wow, wouldn't that be nice!). Last week I got:

10 hours on Sat.

4 hours on Sun.

6 hours on Mon.

4 hours on Tues.

7 hours on Wed.

7 hours on Thurs.

10 hours on Fri.

What is my sleep deficit for this week? Write a program that computes it iteratively.

b. Write a program to compute my deficit recursively.