## CSE 131 Module 6: Recursion

Important!

Before beginning any work, do a Team...Pull in your repository.

### Procedure

Preparation:
• It is suggested that you do this lab with somebody else, in pairs.
• If you choose to work in pairs, both group members must understand all written an coded material.
• Complete your work in either member's repository.
• When you demo, both group members must be present.
• Update your repository so that you see a lab6 package in the labs source folder.
1. Consider the old camp song:
n bottles of beer on the wall, n bottles of beer; you take one down, pass it around, n-1 bottles of beer on the wall.

n-1 bottles of beer on the wall, n-1 bottles of beer; you take one down, pass it around, n-2 bottles of beer on the wall.

and so on down to 0 bottles of beer on the wall.

• Find the recursive substructure in the above song.
• Create a new class Beer in your lab6 package.
Be sure to check the box that asks for public static void main to be generaated.
• In your Beer class, develop a recursive algorithm String bottlesOfBeer(int n) that computes the song starting at n and ending at 0. Your recursive method should not print anything, but when your algorithm is working, print the string finally returned by the recursive method.
• Write code into the main method of Beer to call bottlesOfBeer(5) and print out the string returned by that method.
• Test your program for other input parameters. Be prepared to demo this for a TA to receive credit for this lab.

2. Here is a simple but interesting recursive function.
```   f(x) =    x-10     if x > 100
= f(f(x+11))  if x <= 100
```
• Using the substitution model, sketch the computation of f(99).
Be prepared to show your substitution model computation to a TA when you demo.
• Sketch the computation of f(87).
• Be prepared to answer the following questions about the above code:
• Will this function terminate for all positive integers supplied as arguments.
• What do you expect this function to do for values of x > 100?
• How will it behave for values <= 100?
• In the Methods class, Implement the function, test it to develop or valdiate your hypotheses, and be prepared to demo your function to a TA.

3. Here is another interesting recursive function:
```  g(x,y)  = y+1               if x = 0
= g(x-1,1)          if x > 0 and y = 0
= g(x-1, g(x, y-1)) if x > 0 and y > 0
```
• Using the substitution model, sketch the computations of
• g(1,0)
• g(1,2)
• g(2,2)
• Will this function terminate for all positive integers supplied as arguments?
• How do you expect this function behave with respect to x and y?
• Implement it and try it out for values of x < 4 and various values of y.
• Now try it for x = 4 and various values of y.
• What do you see?
You may be interested to know that the red square button will terminate your application.
• Why does the function behave this way?

4. Consider the picture below.

• Think about what you see: what is foreground and what is background?
• Develop an approach for drawing the figure recursively.
• What is the base case?
• What are the recursive calls doing?
• Create a Triangles class in the lab6 package.
• Implement your ideas in the Triangles class, and be prepared to demo and discuss your code to a TA to receive credit for this lab.

• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
• You must demo the commited work to a TA. Make sure the TA knows that your demo is for credit at this point.
• Follow the directions below to have your demo for this work recorded.

When you are done with this lab, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in the TA's name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for lab 6
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1 Copy from 1 to all others 2 Copy from 2 to all others

Acknowledgements and assertion of integrity