## CSE 131 Module 6: Recursion

Important!

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

### Studio

if necessary, review studio procedures before starting.

### Warmup

• First, form a group of two people, possibly three if there is an odd number in the room.
• All but one member of your group should have this web page open so you can follow along and see the instructions as you work.
• All members of the group should update their repositories:
• Open your repository in eclipse
• Right-click (control-click on a mac) on your repository name
• Drag down to Team...
• Choose Pull
• Supply your bitbucket credentials as needed
• Plan to have one computer at which your team does its work. Initially, one of you will be in charge of typing at that computer.
• Throughout the studio, you should trade who is in charge of the keyboard. Before doing so, commit your work to make sure your work is saved.

Note! It is very important to the pedagogical goals of this studio that you follow the directions below carefully. The object of studio is not to arrive at a solution, but rather to understand the processes involved in developing solutions.

For example, at times, you may be asked to sketch a solution using pencil and paper.

To be blunt, this means you must have pencil and paper out, and you must use said paper and pencil to sketch solutions. These sketches are very helpful both for your own understanding of recursive computations but also these sketches help us understand how you think about recursion.

#### Overview

In this studio you will learn two styles of developing recursive code:
• A recursive specification or formula may be provided for a computation. In such cases, the recursive code is often a direct transcription of the formula into Java.
• Examples or instances of the computation may be provided. In such cases, you must identify the recursive structure of the computation to obtain code.

#### Recursive Formulae

1. For each of the following recursive formulae, write the corresponding code in Java and test your solution using the provided JUnit test.
The functions defined below are partial, in the sense that they do not work on all inputs. Let's assume that inputs to all functions below are restructed to the nonnegative integers (0, 1, 2, …).

Do not worry about errors that may occur if improper inputs are presented.

factorial
This was done in the videos, but try to do it here on your own.
 fact(n) = { n × fact(n-1) n > 0 1 otherwise
Fibonacci
 fib(n) = { fib(n-1) + fib(n-2) n > 1 n otherwise
isOdd
 isOdd(n) = { ! isOdd(n-1) n > 0 false otherwise
sum
 sum(a,b) = { sum(a+1, b-1) b > 0 a otherwise
2. Using the substitution model, show (using pencil an paper) the evaluation of:
• isOdd(3)
• sum(100,3)
At this piont, show your work to a TA before proceeding!

#### Circles

For the following picture:
1. Using pencil and paper identify the base case (that is: a terminating scenario that does not use recursion to produce an answer).
2. Using pencil and paper identify the recursive sub-structure (that is: the compuation that is smaller than the larger one).
4. Open the file Circles.java in the studio6 package and note that the provided main sets the StdDraw world (-1,-1) to (1,1) and initiates recursiveCircles centered at (0,0) with a radius of 0.5:
```public static void main(String[] args) {
StdDraw.setXscale(-1, +1);
StdDraw.setYscale(-1, +1);
recursiveCircles(0, 0, 0.5);
}```
5. Implement the recursive method recursiveCircles to draw the picture above:
private static void recursiveCircles(double xCenter, double yCenter, double radius)

#### Recursive Substructure

Below are some computations you have seen before, but we will now conceive of them recursively. Using pencil and paper, identify the recursive substructure as shown in the videos. This means circling the compuation that is smaller than the larger one, and identifying by name as a function call.

After identifying the substructure, implement the function recursively in Java and run the unit test.

Show your recursive structure diagrams to a TA for each problem below before coding it or before proceeding to the next problem.
factorial
This was done in the videos, but try to do it here on your own.
• fact(n) = n × (n-1) × (n-2) × … × 1
• fact(0) = 1
sumDownBy2
• sumDownBy2(n) = n + (n-2) + (n-4) + …
• sumDownBy2(1) = 1
• sumDownBy2(0) = 0
harmonicSum
• harmonicSum(n) = 1 + 1/2 + 1/3 + … + 1/(n-1) + 1/n
• harmonicSum(1) = 1
NB: The result of this computation should be a double. Be careful about integer divsion!
mult
•  mult(a,b) = a + a + … a + a | Added together b times | mult(a,0) = 0

#### Cantor Stool

Create the necessary class file and whatever methods necessary to implement the recursive drawing below:

#### Bottles of Beer on the Wall

• 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 studio6 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 studio.

#### Substitution Model A

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

#### Substitution Model B

• 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?

• If your studio contains a feedback.txt file, respond to the questions and supply any requested information.
• 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.

When you are done with this studio, 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 studio 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 3 Copy from 3 to all others 4 Copy from 4 to all others

Acknowledgements and assertion of integrity