# Examples
1. Write a function that calculates the nth Fibonacci number
2. Write a function that reverses a string
```java
int fib(int n) {
if (n==1) return 1;
if (n==2) return 1;
return fib(n-1) + fib(n-2);
}
String myReverse (String s) {
if (s.equals("")) return "";
String head = s.substring(0,1);
String tail = s.substring(1);
return myReverse(tail) + head;
}
```
# Number Problems
1. 6! (6 Factorial) = 6x5x4x3x2x1. Write a recursive function fac that returns the factorial of a number. Example: fac 4 returns 24
2. The first 6 triangle numbers are 1, 3, 6, 10, 15. The nth triangle number is 1 + 2 + 3 + ... + n. Write a recursive method to find the nth triangle number
3. Write a recursive function pow m n that returns m to the nth power. Example: pow 2 3 returns 8.
4. The Harmonic Series begins 1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/n. Write a recursive method that finds the sum up to the nth term.
5. From Wikipedia: The Collatz conjecture is a conjecture in mathematics that concerns a sequence defined as follows: start with any positive integer n. Then each term is obtained from the previous term as follows:
- If the previous term is even, the next term is one half the previous term.
- Otherwise, the next term is 3 times the previous term plus 1.
- The conjecture is that no matter what value of n, the sequence will always reach 1.
- Write a recursive function that applies the sequence to a number n. Note that if the conjecture is true, your function will always return 1, it may just take some time to do this!
- Hint: use ``n `div` 2``rather than n/2 to stop Haskell being picky about types.
## Extension
Modify the above question so that it counts the number of steps before reaching 1
# String Problems
1. Write a function that reverses a string
2. Remove the "e"s from a sentence. Example: noEs "cheddar cheese" returns "chddr chs"
3. Write a recursive method called reduce() that returns a String with repeated characters removed. Example: reduce("mmmississippi") returns "misisipi"
4. Count the number of times "e" appears in a string. Example: countE("cheddar cheese " will return 3.
5. Separate a string: "From this" to "F r o m t h i s"
## Extension
1. Check that empty parentheses match: ((())) or (()) but not (()
2. Check parentheses match in a string "((this) (could (be)) (an example))"
[[Java Recursion Solutions]]