Ricorsione

1. Scrivere una Successione che implementi due metodi statici fact e fib che accettano come argomento un numero intero \(n\) e restituiscono, rispettivamente, il fattoriale di \(n\) e l'\(n\)-esimo numero della sequenza di Fibonacci. L'implementazione, ricorsiva, dei due metodi è già stata vista e discussa a lezione.
2. Considerare l'algoritmo di ricerca binaria spiegato durante la lezione sugli array. Realizzare la classe ArrayUtils che implementi un metodo statico RecursiveBinarySearch che accetta come argomento un array già ordinato e un valore, e che effettui la ricerca del valore nell'array sfruttando un algoritmo ricorsivo.
3. Aggiungere alla classe ArrayUtils dell'esercizio precedente un metodo statico mergeSort che accetta come argomento un array e lo ordina secondo il seguente algoritmo:
   1. se l'array ha lunghezza \(0\) o \(1\) restituisce l'array stesso
   2. se l'array ha lunghezza \(2\) restituisce l'array ordinato
   3. se l'array ha lunghezza \(n > 2\) invoca il metodo mergeSort sull'array composto dagli elementi dalla posizione 0 alla posizione \(\frac{n}{2}\) e sull'array composto dagli elementi dalla posizione \(\frac{n}{2} + 1\) alla posizione \(n - 1\), fondendo successivamente questi due array in modo da mantenere l'ordine.