08 Jun check the attachment
Recursion
Question 1:(15 marks)Draw run-time stack (one stack frame for each method call)showing all recursive calls that are made when computing f(10) for the Java method below, and using your run-time stack, compute f(10).
public static int f(int n) { if (n < 2) return n;
else if (n % 2 == 0) return f(n/2) + f(n/3); else return f(n-1) + f(n-2);
}
Question 2: (85 marks)
Write a complete recursive java program to compute the heights of the tick marks on a ruler. Assume that the length of the ruler is a power of 2 (say L=2^n, where n >=1) , and the marks are to be placed at every point between 0 and 2^n, not including the endpoints. The endpoints 0 and 2^n will have height 0. Here are the rules for computing the heights of the ticks for a ruler of length L=2^n:
- The middle point of the ruler has height log(L), where the logarithm is base 2. Stop if L <= 2.
- Break the ruler into two equal halves of length L/2 each and set L=L/2
- Repeat step 1 for both halves resulting from step 2.
You may use an array of the appropriate size to hold the heights. When printing your output, print the heights on one line, and the position of the points below. For the printing of the positions of the points, just print the last digit of the position. Here is an example for n=8.
012131210
012345678
Here is an example for n=16.
01213121412131210
01234567890123456
Your program should prompt the user for an integer, check to make sure the length entered by the user is a power of 2 and at least 2. To check if a number is a power of 2,
you need the Math.log and Math.round methods. Be careful that the Math.log routine in Java is base e (not base 2). You will need to do the appropriate conversion between base 2 and base e. Finally, your program should print the heights of the ruler’s points as illustrated above.
Extra Fun(not for marks): How (if it is even possible) do you solve this problemwithout recursion?
Submission:
1) Upload your source code for Question 2 on CMS.
2) Draw the solution for question 1. Submit a printout of your program for question 2 along with a copy of the output generated by running the program.
3) Arrange to meet one-to-one with your TA to do a short demonstration of your program in the lab and answer a few questions about the coding on due date or before.
Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.
About Writedemy
We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.
How It Works
To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Are there Discounts?
All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.