# CSE1030Z Week 09 Homework Problems

Recursion

## 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

`String reverse(String s)`

that returns the string equal to the characters in `s` in reverse order. For example, `reverse("banana")` returns `"ananab"`.
4. Implement a recursive method with signature

`String replace(char c, char with, String s)`

that returns the string equal to the string `s` with all characters equal to `c` replaced with the character `with`. For example, `replace('a', 'u', "banana")` returns `"bununu"`.

## Moderate Problems

1. Implement a recursive method with signature

`int binarySearch(List<String> t, String s)`

that uses binary search to find an element `s` in a sorted list `t` of strings. Binary search recursively examines the middle element of the list to determine which half of the list the target word `s` must lie in (much like the bisection method for root finding). Your method should return the index of the string `s` if it is in the list, otherwise it should return -1.

Coming soon.

Coming soon.