Assignment 6: Recursion

Procedure

Preparation:

Update your repository so that you see a lab6 package in the labs source folder.

  1. 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 lab6 package.

    Be sure to check the box that asks for public static void main to be generated.

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

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

  3. 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?
  4. Consider the picture below.

    • Think about what you see: what is foreground and what is background?

    • Develop an approach for drawing the figure recursively.

      • What is the base case?

      • What are the recursive calls doing?

    • Create a Triangles class in the lab6 package.

    • Implement your ideas in the Triangles class, and be prepared to demo and discuss your code to a TA to receive credit for this lab.

Sierpinski Triangle