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


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:

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:
    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).
  3. Get your answers checked off by a TA
  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.
sumDownBy2
harmonicSum
NB: The result of this computation should be a double. Be careful about integer divsion!
mult

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.

    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
    

    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
    

    Submitting your work (read carefully)



    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.

    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

    You must select one of the options below
    The work submitted here was performed in accordance with this course's policy on collaboration.
    On your honor, you have neither given nor received any unauthorized aid on this assignment.

    However, the following TAs, students, or professors were supportive in completing this assignment.
    Their help was also in accordance with course policies.

    Thanks to (leave blank if appropriate):

    In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment.

    You would like to be contacted by an instructor to facilitate staying on track in this course.

    Comments about this:

    You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment.

    You would like to be contacted by an intructor to faciliate staying on track in this course.

    Comments about this:


    TAs double check!
    • This demo box is for studio 6
    • The student has committed and pushed the work, and verified that it appears at bitbucket.
    TA: Password: