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.
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.
fact(n) = | { | n × fact(n-1) | n > 0 |
1 | otherwise |
fib(n) = | { | fib(n-1) + fib(n-2) | n > 1 |
n | otherwise |
isOdd(n) = | { | ! isOdd(n-1) | n > 0 |
false | otherwise |
sum(a,b) = | { | sum(a+1, b-1) | b > 0 |
a | otherwise |
At this piont, show your work to a TA before proceeding!
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.
NB: The result of this computation should be a double. Be careful about integer divsion!
mult(a,b) = | a + a + | … | a + a | |
| | Added together b times | | | ||
mult(a,0) = | 0 |
When you done with this studio, 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