# Examples
1. The Fibonacci Sequence begins 1,1,2,3,5,8,13,21... Each number in the sequence is the sum of the two preceding ones. Write a method fib(int n) that returns the nth number in the Fibonacci Sequence. Test your method as follows: fib(1) returns 1, fib(4) returns and fib(8) returns 21
2. Write a method reverse(int \[\] numbers) that returns the elements of an array in reverse order. Test your method with the array {1,2,3,4,5}. It should return the array {5,4,3,2,1}
# Non-Recursive Java Solutions
```java
public class MyClass {
public static void main(String[] args) {
System.out.println(fib(3));
System.out.println(fib(4));
System.out.println(fib(5));
System.out.println(fib(6));
int [] nums = {1,2,3,4,5};
for (int n: reverse(nums)){
System.out.println(n);
}
}
static int fib(int n){
if (n<3) return 1;
int first = 1;
int second = 1;
int fib = 2;
for (int i = 2; i <n; i++){
fib = first + second;
second = first;
first = fib;
}
return fib;
}
static int[] reverse(int [] numbers){
int [] nums = new int[numbers.length];
for (int i =0; i<numbers.length; i++){
nums[numbers.length - i-1] = numbers[i];
}
return nums;
}
}
```
# Recursive Haskell Solutions
```haskell
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
```
# 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
# List Problems
Find the minimum value in a list. Example: minimum' \[1,3,2\] returns 1
```haskell
minimum' [x] = x
minimum' (x:xs) = min x (minimum' xs)
```
1. Work out the product of a list (multiply all the numbers together) Example: product' \[2,3,4\] returns 24
2. Count the number of zeroes in a list. Example: noZeroes \[1,0,3,0,4\] returns 2
3. Count the number of times an element appears in a list. Example numElem 4 \[1,4,2,4,5\] returns 2
4. Find last element in a list
5. Take the first n elements from a list. Example: take' 3 \[a,b,c,d,e\] returns \[a,b,c\]
6. Duplicate a list. Example: duplicate' \[a,b,c\] returns \[a,a,b,b,c,c\]
## Extension
Remove repeated elements from a list. Example: reduce' \[a,a,b,c,d,d,e\] returns \[a,b,c,d,e\]
[[Haskell Recursion Solutions]]