Description
The purpose of this assignment is gaining practice in recursive programming. Therefore, in
each exercise, you must provide a recursive solution; other solutions will not be accepted.
Your implementation may or may not include private functions, as you see fit.
1. Golden ratio
Write a class called GoldenRatio that takes an integer input N and computes an
approximation to the golden ratio using the following recursive formula:
�(�) = & 1, �� � = 0
1 + 1⁄�(� − 1) , �� � > 0
You are required to implement two functions:
• goldenRec(n) that calculates the golden ratio using recursion.
• goldenIter(n) that calculates the golden ratio using iteration.
A main, which is already supplied, will print the results of both the recursion and the iteration.
2. Permutations
A permutation of n elements is one of the n! possible orderings of the elements.
Write a class called Permutations that takes an integer command-line argument n and prints
all n! permutations of the first n letters of the alphabet, starting at a (assume that n is no
greater than 26).
For example, when n = 3 you should get the following output (but do not worry about the
order in which you enumerate them):
> java Permutations 3
bca cba cab acb bac abc
Hint: Before you start thinking of the code, try to write on a piece of paper all the
permutations of “abcd”.
3. First TTH
Probabilities can sometimes be calculated using recursion. For example, the probability of
winning at least one coin flip out of ten coin flips (Q(10)) equals the probability to win the
first flip (Q(1)), plus the probability to lose the first flip (1-Q(1)) and then to win at least one
of nine coin flips (Q(9)). Importantly, the probability to win just a single coin flip is exactly
½. Therefore,
Q(n) = Q(1) + (1-Q(1)) * Q(n-1) = ½ + ½ Q(n-1).
In that spirit, suppose we flip a coin multiple times, resulting in a sequence of heads (H) and
tails (T). We stop flipping the coin when we get the sequence TTH (tail-tail-head). What is
the probability that we have flipped exactly n coins?
For example, these are sequences of nine coin flips that end with the first TTH:
Introduction to CS, IDC Herzliya, 2019-2020 / Homework 7 / page 2
HHTHHHTTH, THHHHTTTH, HTHTHHTTH, THTTTTTTH
These are not sequences of nine coin flips that end with TTH, either because TTH already
appears before the end, or because they do not end with TTH:
TTTTTHTTH, HTHHTHTTT, HTHTTHTTH, TTTTTTTTT
Write a class called TTH that takes a single command-line argument n and prints the
probability P(n) of flipping exactly n coins and get TTH on the last three flips.
Important: the calculation of P(n) must be done recursively. To do so, note that a sequence of
n coin flips that ends with the first TTH must fulfill one of the following:
1. Start with H followed by a sequence of n-1 flips that ends with the first TTH.
2. Start with TH followed by a sequence of n-2 flips that ends with the first TTH.
3. Start with n-1 Ts, followed by an H.
This can also be represented by the following formula:
P(n) = Prob(H) * P(n-1) + Prob(TH) * P(n-2) + Prob(n-1 Ts) * Prob(H)
=½ P(n-1) + ¼ P(n-2) +1/2n
where Prob(X) is the probability for X to occur.
Use this formula to implement a recursive function calcP(n) that calculates P(n).
Examples:
> java TTH 2
0.0
> java TTH 3
0.125
> java TTH 10
0.052734375
> java TTH 20
0.006450653076171875
5. Memoization
The calculation we did above for P(n) was wasteful: P(5) is calculated using P(4) and P(3),
and P(4) also uses P(3), but it re-calculates it.
To avoid this wastefulness, we can use memoization. This technique is very powerful: the
time to calculate P(20), for example, is 100-fold longer without memoization.
To use memoization, we initialize a memory array double[] memory that saves the results of
P(n) values that we have already calculated. This array is passed to the recursive function.
Then, when attempting to calculate a P(n) value inside the function calcPmem, we:
Introduction to CS, IDC Herzliya, 2019-2020 / Homework 7 / page 3
1. If P(n) is not in the memory, we calculate it and put it in the array;
2. Return the value of P(n) from the memory.
Note that P(n)>0 for n>2, so we can initialize the memory array to zeros at the beginning and
then fill in the values of P(n) as we go along.
Add another function calcPmem(int n, double[] memory) that calculates P(n) while using
memoization.
5. Fractal Tree
A random fractal tree can be generated using the following fractal rule:
a. Randomly choose a branch length.
b. Adjust branch color and width.
c. Draw a branch.
d. Repeat to draw two branches at the end of the drawn branch with two random angles.
e. Stop when you reach a specified recursion depth.
You can see an example of a full tree (recursion depth of 14) at the bottom of this page and
watch an animation of the tree been drawn in this link.
Write a function in the class FractalTree that draws a random fractal tree with given level n, using
the signature
public static void drawBranch(int level, double x0, double y0, double length, double
angle).
A corresponding main function, as well as some constants, are already given.
Implementation details:
– The length of the line you draw at each call to drawBranch should be a random number
between 0 and length.
– The maximum length of the branch (length) starts at 100 for the trunk and is reduced by a
factor of 0.8 at each level of the tree.
– The angle of the branch you draw at each call should be exactly angle.
– The color of the branch should be adjusted at each call such that the red, green, and blue
values are a weighted average of the color of the root (rootColor) and the color of the leaves
(leafColor). The weight is the ratio between the current recursion depth (level) and the
maximal recursion depth (recursionDepth). For example, the red value should be
rootRed * w + leafRed * (1-w) where w = level / recursionDepth.
– The width should be adjusted to be trunkWidth * w (where w is the same as above), but not
lower than minWidth.
– The angles of the next branches should be randomly chosen:
o For one branch, the angle should be between the current
angle (angle) plus a random value between 0 and π/4 * m,
where m=6/level.
o For the other branch, the angle should be the current angle
minus a random value between 0 and π/4 * m, where
m=6/level.
– The root of the tree should have the highest level. Make sure to
decrement level, and to halt when it reaches zero.
Introduction to CS, IDC Herzliya, 2019-2020 / Homework 7 / page 4
Submission
Before submitting your solution, inspect your code and make sure that it is written according to our
Java Coding Style Guidelines. Also, make sure that each program starts with the program header
described in the Homework Submission Guidelines. Both documents can be found in the Moodle
site, it is your responsibility to read them. Any deviations from these guidelines will result in points
penalty. Submit the following files:
➢ GoldenRatio.java
➢ Permutations.java
➢ TTH.java
➢ FractalTree.java
Deadline: Submit Homework 7 no later than January 12, 23:55. You are welcome to submit
earlier.
