Assignment 6: Recursion
Procedure
Preparation:
Update your repository so that you see a lab6 package in the labs source folder.
-
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
Beerin yourlab6package.
Be sure to check the box that asks for
public static void mainto be generated.-
In your
Beerclass, develop a recursive algorithmString 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
Beerto callbottlesOfBeer(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.
-
-
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
Methodsclass, implement the function, test it to develop or valdiate your hypotheses, and be prepared to demo your function to a TA.
- Using the substitution model, sketch the computation of
-
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?
-
-
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
Trianglesclass in thelab6package. -
Implement your ideas in the
Trianglesclass, and be prepared to demo and discuss your code to a TA to receive credit for this lab.
-
