EECS2030 Recursion programming questions

Solutions

Solutions can be found here

Short Problems

1. Implement a recursive method with signature
   
   int sum(int n)
   
   that computes the sum of the integers 1, 2, ..., n.
2. Implement a recursive method with signature
   
   long factorial(int n)
   
   that computes the factorial of n, n! = 1 * 2 * ... * n.
3. Implement a recursive method with signature
   
   boolean isPrime(int x, int divisor)
   
   that determines if the positive integer x is a prime number. Note that x is not prime if x % divisor == 0 when divsior is not equal to 1 or x. You may assume that the client invokes this method starting with a divisor of 2
4. Implement a recursive method with signature
   
   String reverse(String s)
   
   that returns the string equal to the characters in s in reverse order. For example, reverse("banana") returns "ananab".
5. Implement a recursive method with signature
   
   String everySecondChar(String s, int idx)
   
   that returns the string formed by concatenating every second character in s starting from index idx. For example, everySecondChar("banana", 0) returns "bnn", and everySecondChar("banana", 1) returns "aaa"

Moderate Problems

1. Implement a recursive method with signature
   
   int sumEven(List<Integer> t)
   
   that computes the sum of the even integers in the list t.
2. Implement a recursive method with signature
   
   List<Integer> allEven(List<Integer> t)
   
   that returns a list of the even integers in the list t.
3. Implement a recursive method with signature
   
   String everySecond(List<String> t, int idx)
   
   that returns the string formed by concatenating every second string in t starting from index idx. For example, suppose that:
   
   t is the list ["a", "b", "c", "1", "2", "3"]
   
   then everySecond(t, 0) returns "ac2",
   everySecond(t, 1) returns "b13", and
   everySecond(t, 6) returns "".
4. • a previous set of 4 problems including proofs of correctness and termination
   • hints
   • full solutions