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
 Rightclick (controlclick 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

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(n1)  n > 0 
1  otherwise 
 Fibonacci

fib(n) =  {  fib(n1) + fib(n2)  n > 1 
n  otherwise 
 isOdd

isOdd(n) =  {  ! isOdd(n1)  n > 0 
false  otherwise 
 sum

sum(a,b) =  {  sum(a+1, b1)  b > 0 
a  otherwise 
 Using the substitution model, show (using pencil an paper) the evaluation of:
At this piont, show your work to a TA before proceeding!
Circles
For the following picture:
 Using pencil and paper identify the base case (that is: a terminating scenario that does not use recursion to produce an answer).
 Using pencil and paper identify the recursive substructure (that is: the compuation that is smaller than the larger one).
 Get your answers checked off by a TA
 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);
}
 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 × (n1) × (n2) × … × 1
 fact(0) = 1
 sumDownBy2

 sumDownBy2(n) = n + (n2) + (n4) + …
 sumDownBy2(1) = 1
 sumDownBy2(0) = 0
 harmonicSum

 harmonicSum(n) = 1 + 1/2 + 1/3 + … + 1/(n1) + 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, n1 bottles of beer on the wall.
n1 bottles of beer on the wall, n1 bottles of beer;
you take one down, pass it around, n2 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) = x10 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(x1,1) if x > 0 and y = 0
= g(x1, g(x, y1)) if x > 0 and y > 0
 Using the substitution model, sketch the computations of
 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?
Submitting your work (read carefully)
 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 topmost level of your repository, which bears your name and student ID.
 Follow the instructions in the green box below to receive credit for your work.
Last modified 01:52:19 CDT 21 October 2018
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.
 Commit and push all your work to your repository.
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 ontime.
 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