NCBC 2006 - Data Structures Assignment #2 Dues Recursion (40 marks) Write a recursive method that has one integer parameter (a) and returns the number of binary strings of length that do not have two consecutive 1. You should not use any loops in your solution. For example, forn - 4 the number of binary strings of length 4 that do not contain two consecutive Isis 8 0000.0001.0010.01000101,1000,10011010 For this problem, your method needs to retum only the number of such strings, not the strings themselves HINT: The number of such strings is the number of strings that start with a plus the number of strings that start with 2. (60 marks) Write a complete recursive java program to compute the heights of the tick marks on a rulet. Assume that the length of the ruler is a power of 2say L-2'n. wheren >I), and the marks are to be placed at every point between 0 and 2n, not including the endpoints. The endpoints and 2'n will have height 0. Here are the rules for computing the heights of the ticks for a ruler of length 1-2 1. The middle point of the ruler has height log(L), where the logarithm is base 2 2. Break the ruler into two equal halves of length 1/2 cach and sett-1/2 3. Repeat step 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.justprint the last digit of the position. Here is an example for 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 c (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 problem without recus Submission: Upload your source code to CMS by due date