# Number Problems
6! (6 Factorial) = 6x5x4x3x2x1. Write a recursive function fac that returns the factorial of a number. Example: fac 4 returns 24
```java
int fac(int n) {
if (n == 0 ) return 1;
if (n == 1 ) return 1;
return n* fac(n-1);
}
```
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
```java
int triangle(int n)
{
if (n == 1) return 1;
return n + triangle(n-1);
}
```
Write a recursive function pow m n that returns m to the nth power. Example: pow 2 3 returns 8.
```java
int pow(int m, int n)
{
if (n == 0) return 1;
if (n == 1) return m;
return m * pow(m, n-1);
}
```
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.
```java
double harmonic(double n)
{
if (n == 1) return 1;
return 1.0/n + harmonic(n-1);
}
```
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!
```java
int collatz (int n) {
if (n == 1) return 1;
if (n%2 == 0) {
return collatz(n/2);
} else {
return collatz(3*n + 1);
}
}
```
## Extension
Modify the above question so that it counts the number of steps before reaching 1
# String Problems
Write a function that reverses a string
```java
String myReverse (String s) {
if (s.equals("")) return "";
String head = s.substring(0,1);
String tail = s.substring(1);
return myReverse(tail) + head;
}
```
Remove the "e"s from a sentence. Example: noEs "cheddar cheese" returns "chddr chs"
```java
String noEs (String s) {
if (s.equals("")) return "";
String head = s.substring(0,1);
String tail = s.substring(1);
if (head.equals("e"))
return noEs(tail);
else
return head + noEs(tail);
}
```
Write a recursive method called reduce() that returns a String with repeated characters removed. Example: reduce("mmmississippi") returns "misisipi"
```java
String reduce (String s) {
if (s.equals("")) return "";
if (s.length()==1) return s;
String head = s.substring(0,1);
String tail = s.substring(1);
if (head.equals(tail.substring(0,1)))
return reduce (tail);
else
return head + reduce(tail);
}
```
Count the number of times "e" appears in a string. Example: countE("cheddar cheese " will return 3.
```java
int eCount(String s) {
if (s.equals("")) return 0;
String head = s.substring(0,1);
String tail = s.substring(1);
if (head.equals("e"))
return 1 + eCount(tail);
else
return eCount(tail);
}
```
Separate a string: "From this" to "F r o m t h i s"
```java
String separate(String s) {
if (s.equals("")) return "";
String head = s.substring(0,1);
String tail = s.substring(1);
return head + " " + separate(tail);
}
```
## Extension
1. Check that empty parentheses match: ((())) or (()) but not (()
2. Check parentheses match in a string "((this) (could (be)) (an example))"