CSE 131 Module 6: Recursion

Studio

if necessary, review studio procedures before starting.

Warmup

• Obtain a studio name from a TA or the professor
• Open the studio repository as usual:
• In eclipse:
Window...Open Perspective...Other...SVN Repository Exploring
• Click on the New Repository Location icon (looks like a gold battery with a green plus sign).
• Copy the following URL using your mouse:
`https://shell.cec.wustl.edu:8443/cse131/svn/studio6-ZZZZZZ`
After pasting:
• Change ZZZZZZ to the word on your sticker. For example, hockey.
• If the repository is validated, keep going; otherwise get help.
• Right-click on the project name and Check Out the workspace.

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 front of you during lecture.
 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!

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 lecture. 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 front of you during lecture.
• 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

• 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 done with this studio, you must be cleared by the TA to receive credit.
• 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

Studio repo name: studio6- (from your sticker)

 Last name 1 2 3 4 5 6