change the EC? its too similar to endx i think? do another on there
These labs will be due Monday 2/9 at 11:59pm in google drive. You will submit RecursionBasics.java and RecursionFun.java to your google drive folder. You can view a video version of this lesson here: https://www.youtube.com/watch?v=DFktvZAvs9s and https://www.youtube.com/watch?v=I4hEQAgaPio
As a special instruction for this lab - you should do the entire lab WITHOUT using a for or a while loop. Everything should be done using recursion. Very few, if any, methods require more than 5 lines of code. Expect to spend a lot of time thinking, experimenting and testing! As always, make sure your method names and class names (as well as inputs and outputs) match mine EXACTLY.
If you are stuck, the following meme should help you out: https://drive.google.com/file/d/1Z3u3DQjwuQDqjq4-Kwma5-rey7O_CsoK/view?usp=sharing
Part 1 - RecursionBasics.java (please make sure to spell this and any method names exactly the same as I have done). All code must be written recursively – you should not have ANY for or while loops inside your methods. Your class must have the following 5 STATIC methods:
a. factorial – this method should input a nonnegative int (you may assume no one will not enter a negative number, you don’t need an extra if statement or anything) return an int representing n! (remember 5! = 5*4*3*2*1)
b. sumN – this method should input a positive int and return an int representing the sum of every integer from 1 to that number. For instance, sumN(5) should return 15 (because 15 = 1+2+3+4+5).
c. sum1N - this method should input a positive int and return a double representing the sum of every fraction with a 1 on top from 1 to that number. For instance, sum1N(4) should return whatever 1/4+1/3+1/2+1 is (2.083333333), and sum1N(2) = ½ + 1 = 1.5.
d. sumNalt - this method should input a positive int and return an int representing the sum of every integer from 1 to that number, EXCEPT now the terms will alternate between positive and negative! Note that 1 will always be positive, 2 will always be negative, and so on. So it should add 1 – 2 + 3 – 4 + 5… For instance, sumNalt(4) should return -2 (which is -4 + 3 - 2 + 1) and sumNalt(5) will return 3. You will need some if/elses inside your method to deal with odds/evens. Be careful to not switch the signs of all the terms at once!
e. public static int countX(String str)
Given a string, compute recursively (no loops) the number of lowercase 'x' letters in the string. You can use either substring or indexOf to just look at one spot at a time.
countX("xxhixx") → 4
countX("xhixhix") → 3
countX("hi") → 0
Part 2. Create a class named RecursionFun. The following methods should ALL be static :
a. public static int count7(int n)
Given a non-negative int n, return the count of how many 7s appear in n as a digit, so for example 717 yields 2. (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).
count7(717) → 2
count7(7) → 1
count7(1234692) → 0
b. public static int powerN(int base, int n)
Given base and n that are both 1 or more, compute recursively (no loops) the value of base to the n power, so powerN(3, 2) is 9 (3 to the 2nd power). Obviously you should not use Math.pow().
powerN(3, 1) → 3
powerN(3, 2) → 9
powerN(3, 4) → 81
c. power2 – this method should input an int and return a boolean that represents whether the number is a power of 2. For instance power2(64) should return true because 64 = 2^6, but power2(10), power2(0), power2(-8), power2(3) should all return false because we cannot write them in the form 2^n.
(HINT: what happens to a power of 2 if you divide by 2 repeatedly? What happens to something that is not a power of 2 if you divide by 2 repeatedly? You should use %)
d. fibonacci – this method should input an int n (you may assume n will not be negative) and return the nth Fibonacci number (recall the pattern is 0,1,1,2,3,5,8,etc. where each number is the sum of the two numbers before it). We will use the same numbering system as in this excellent resource (http://en.wikipedia.org/wiki/Fibonacci_number), so fibonacci(0) = 0, fibonacci(1) = 1, fibonacci(2) = 0 + 1 = 1, fibonacci(3) = 2, fibonacci(6) = 8. This is a perfect example of a problem that is much more difficult to do with for/while loops.
(HINT: you will want to use 2 base cases for this one. This one is deceptively easy....)
e. gcf – this method should input two positive integers and return the GCF (greatest common factor) of those two integers, also an int. So gcf(5,7) should return 1, gcf(8,12) should return 4, and gcf(203,203) should return 203. I recommend Euclid’s algorithm, which follows like so:
-If the two numbers are the same, the GCF of (a,a) = a
-If one number is bigger, subtract the smaller number from that number, then take the GCF of the difference and the smaller number. For instance:
To find gcf(12,8), 12 is bigger than 8, so subtract 12-8 (get 4), then replace the 12 with the difference, go gcf(12,8) = gcf(4,8). Now 8 is bigger than 4, so subtract the smaller number, so 8-4=4, replace that, so gcf(4,8)=gcf(4,4) which = 4.
(your program should give the same answer for gcf(12,8) as it does for gcf(8,12) )
In case you are curious, this problem is much more difficult without recursion.
f. endX - this method will input a String and recursively move all the lower case x's to the end of the String, keeping the rest in order, and return that String. For example:
endX("xxre") -> returns "rexx"
endX("xhixxhix") -> "hihixxxx"
endX("boo") -> "boo"
(HINT: Your recursive call will be slightly more convoluted here! You might want to do something like this: return endX(something) + "x"; make sure you do not have an infinite recursion)
g. sumToEnd(int[ ] arr, int x) - this method inputs an array of ints called arr and an integer x, and should return the sum of all elements from spot x through the end of the array, computed recursively (no loops allowed!).
For example, if arr is [16,-3,25,9,10],
sumToEnd(arr, 0) should return 57
sumToEnd(arr,2) should return 44 (25 + 9 + 10)
sumToEnd(arr,4) should return 10
You may assume that x will be within the bounds of the loop: so 0 <= x < arr.length
h. (optional) you should also write a main to help you test your methods. I recommend blueJ.
Extra Credit: Do the assignment noX under recursion 1 on www.codingbat.com - email me if you choose to do this and make sure you save it on your account using my email (gborish@hartdistrict.org) under teacher share