## CSE 131 Module 6: Recursion

### 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 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.

Last modified 09:53:05 CDT 16 May 2016
When you done with this lab, you must be cleared by the TA to receive credit.
• Commit all your work to your repository
• 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 his or her 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? (or your numeric ID) Do not propagate e.g. Smith j.smith 1 Copy from 1 to all others 2 Copy from 2 to all others