E7 – Prof. Alam Fall 2019, UC Berkeley
Homework Assignment 8
Recursion
The purpose of this lab is to give you more practice in the application of probability and
introduce you to recursion with more focus on the recursion part. Since we are dealing
with recursion, be very careful with infinity loop.
Note: Use the template provided (HW8 Template.m) in the assignment download to com-
plete this assignment. The template has a very specific format to enable auto-grading, and if
the format is altered your assignment may not be properly graded (this will be apparent to
you). Please also notice that variables in BOLD FONT will be checked to calculate you
grade. In addition, the template file already reflects much of the content of the assignment.
The due time is 11:59am Nov 8th, 2019. NO LATE HOMEWORK WILL BE
ACCEPTED. Please upload the following files through the bCourses website:
• HW8 Solution.m
• HW8.pdf
• Every functions you produced during homework
• All generated plot files
Directions to upload files can be found here.
1. Monte Carlo Simulation
The purpose of this problem is to write a simple Monte Carlo simulation to estimate the
constant π. Further information about Monte Carlo Simulation can be found here. This
is done by first constructing a square with sides of length L. The square is covered with
a circle of diameter L. Particles are randomly dropped on the entire square generated
y a uniform distribution, which means all locations are equally probable. The numbe
of particles within the circle are counted. As the total number of particles increases,
the proportion of particles in the circle to the total number of particles approaches π
4
,
which can be seen from Figure 1.
(a) Write a function piMC with the function declaration line:
1 function [pi est] = piMC(n)
1
https:
guides.instructure.com/m/4212/l/54353-how-do-i-upload-a-file-to-my-assignment-submission
https:
www.palisade.com
isk/monte_carlo_simulation.asp
E7 – Prof. Alam Fall 2019, UC Berkeley
Figure 1: the Monte Carlo simulation
which estimates π by simulating the dropping of n particles onto a circle/square
combo described above. In the first line of your function, add this command
‘rng(1)’. This command ensures that the random generator always produces the
same sequence of random numbers and this is usually used to debug codes. Hint:
For this problem, we can assume L is equal to 1.
(b) Let the e
or e(n) = |πest − π|, where πest is calculated by the function piMC.
Create an E
or a
ay which contains e(n) for n = 100, 1000, 10000, and 100000
and plot log(e(n)) as a function of log(n). The x and y axis labels should be ‘The
natural logarithm of number of Particles’ and ‘Approximation’. The title should
e ‘Monte Carlo Simulation’. Save the plot as .png file named ‘piMC.png’(generate
.png file by the code).
2. The Golden Ratio
Type the following at the command prompt.
1 axis([ XXXXXXXXXX]);
2 rectangle('Position',[ XXXXXXXXXX]);
3 rectangle('Position',[ XXXXXXXXXX]);
4 rectangle('Position',[ XXXXXXXXXX]);
2
E7 – Prof. Alam Fall 2019, UC Berkeley
Which rectangle is more pleasing to your eyes? (You don’t need to include this answe
in your report.)
It is thought that rectangles where the ratio of the sides is close to the Golden Ratio are
considered well-proportioned and “more pleasing”. Many buildings and artworks have
the Golden Ratio in them, such as the Parthenon in Greece, Figure 2. The Golden Ratio
Figure 2: the Parthenon in Greece
is defined as the limit of the sequence of the (m+1)th Fibonacci number divided by the
mth Fibonacci number as m approaches infinity. Recall: The mth Fibonacci numbe
is defined recursively with, F (1) = 1, F (2) = 1, and F (m) = F (m− 1) + F (m− 2) fo
m > 2. For example F (3) = 2, F (4) = 3 and F (5) = 5.
Define the mth Golden Ratio to be myGoldenRatio(m) = F (m)
F (m+1)
,m > 2, where
F (m) is the mth Fibonacci number. You are not allowed to use any for, while loop in
this problem.
(a) Write a recursive Matlab function myFibonacci that takes m as input and re-
turns the mth Fibonacci number F .
1 function F = myFibonacci(m)
(b) Program a Matlab function myGoldenRatio that takes m as input and returns
the mth Golden Ratio R using your function in part (a).
1 function R = myGoldenRatio(m)
(c) Use your function to find the 5th, 10th, and 15th Golden Ratio and store them in
a 1-by-3 a
ay G. Hint: Using command “format long” to see numbers up to 15
decimal places.
3
E7 – Prof. Alam Fall 2019, UC Berkeley
3. Express a number as sum of powers
In this problem, we gonna study how to use recursion to count ways to express a numbe
as sum of powers. Given two integers x and n, we want to get the number of ways to
express x with n-th power of unique positive integers. You are not allowed to use any
for, while loop in this problem.
For example,
Input : x = 100, n = 2
Output : 3
Explanation: There are three ways to express 100 as sum of positive integers raised to
power 2.
100 = 102 = XXXXXXXXXX = XXXXXXXXXX + 72
Input : x = 100, n = 3
Output : 1
Explanation : The only combination is,
100 = XXXXXXXXXX
We can solve this problem by two steps.
(a) First we can build a function Countsumi which takes x(the number to be ex-
pressed), mypower(power) and a positive integer i, we use function Countsumi
to count the number of ways to express x by mypower-th power of the unique
positive integers which are greater or equal to i. The function Countsumi will
e recursive.
1 function Num = Countsumi(x, mypower, i)
(b) Based on the function Countsumi, then we can start to build Countsum, it will
output number of ways Num to express x as sum of mypower-th powers of unique
positive integers. The only difference between Countsumi and Countsum is the
ange of unique positive integers being used to express the target number x.
1 function Num = Countsum(x, mypower)
4. Pascal’s triangle
Pascal’s triangle is a triangular a
ay containing certain integers, which is named afte
the French mathematician Blaise Pascal XXXXXXXXXXIt is known as Pascal’s triangle in
much of the Western world, although other mathematicians studied it centuries before
him in India, Persia, China, Germany, and Italy.
The triangle starts with a 1 on the top row. From there, each entry in a row is equal
4
E7 – Prof. Alam Fall 2019, UC Berkeley
to the sum of the 2 numbers directly above it. If one of those two numbers does not
exist, then a 0 is used, hence the left and right edges of the triangle are composed only
of ones. Figure 3 graphically shows how each element in the triangle is created.
MATLAB does not work with triangular-shaped matrices, so you will be creating a
so-called left-justified Pascal’s triangle, as shown in Figure 4.
You will write a recursive function that determines the value of an element given row
and column numbers in the left-justified Pascal’s triangle. You are not allowed to use
any for, while loop in this problem. This function should have the following declaration
line:
1 function value = pascalsTriangle(row,col)
Figure 3: Summing diagonal elements to create each successive element.
Figure 4: Left justified Pascal’s triangle.
Test your function by following ways.
5
E7 – Prof. Alam Fall 2019, UC Berkeley
1
pascalsTriangle(5,1)
2 ans =
3 1
4
pascalsTriangle(6,4)
5 ans =
6 10
7
pascalsTriangle(8,5)
8 ans =
9 35
BTW, based on the structure left-justified Pascal’s triangle, the input row should be
greater or equal to the input col.
5. The Towers of Hanoi is a famous mathematical game in which there are three pegs
with several discs of varying diameter on one of the pegs. The discs are stacked such
that no disc is on top another disc of greater diameter (see Figure 5). The objective is
to move all of the discs to another peg while abiding by three rules:
(a) Only one disc may be moved at a time;
(b) only the top disc of any stack may be moved;
(c) larger discs cannot rest on smaller discs.
Figure 5: The Tower of Hanoi
The fastest solution involves recursively
eaking down the problem into smaller prob-
lems: a tower is moved by moving all the discs except the bottom, and then moving
the bottom. This remains the strategy until a ‘tower’ is a single disc, when moving
among pegs becomes trivial.
Let’s write a Matlab function which will give you the instruction of moving the towe
of Hanoi as followings. You are not allowed to use any for, while loop in this problem.
1 function instruction = hanoi(d,origin,inter,target)
(a) d: the number of discs on the initial tower.
6
E7 – Prof. Alam Fall 2019, UC Berkeley
(b) origin: the peg on which the discs are originally stacked.
(c) inter: an intermediate peg used for transfe
ing discs.
(d) target: the final peg on which the discs should be stacked.
The origin, inter, target all are 1-by-1 character a
ays. Your function will give
instructions to instruction, which will be a 2-D character a
ays with each row co
e-
sponding to one move. For example,
1
instructions = hanoi(2,'1','2','3')
2 instructions =
3 'Move one disk from peg 1 to peg 2'
4 'Move one disk from peg 1 to peg 3'
5 'Move one disk from peg 2 to peg 3'
6
7
tellmehow = hanoi(3,'A','B','C')
8 tellmehow =
9 'Move one disk from peg A to peg C'
10 'Move one disk from peg A to peg B'
11 'Move one disk from peg C to peg B'
12 'Move one disk from peg A to peg C'
13 'Move one disk from peg B to peg A'
14 'Move one disk from peg B to peg C'
15 'Move one disk from peg A to peg C'
Hint: You may want to initially assign an empty string to output inst. That is, inst
= ‘’.
Be sure to verify that your code solves the problem by inputting a 4-disc tall tower to
e transfe
ed from peg 1 to peg 2 and and checking!
6. Palindrome numbe
A palindromic number (also known as a numeral palindrome or a numeric palindrome)
is a number that remains the same when its digits are reversed. Like 16461, for example,
it is ”symmetrical”. The term palindromic is derived from palindrome, which refers
to a word (such as rotor or racecar) whose spelling is unchanged when its letters are
eversed. The first 30 palindromic numbers (in decimal) are: