The first solution uses recursion and is the simplest. In pseudocode it is:

int fibonacci$($int n$)$

if$($n $==0)$ return $0$

if$($n $==1)$ return $1$

return fibonacci$($n$-1)+$ fibonacci$($n$-2)$

Very simple. Too simple as we will find out. The second method uses dynamic programming to store the previous calculations rather than re$-$calculating them. This one looks like:

int fibonacci$($int n$)$

v$1=0,$ v$2=1,$ v$3=0$

for$($i$=2$ to i $<=$ n$)$

v$3=$ v$1+$ v$2$

v$1=$ v$2$

v$2=$ v$3$

Objective: Implement both methods of solving the Fibonacci sequence into two separate classes that extend the Thread class. The threads will have some way to set n before the thread is started. In the run$()$ function, you will execute the algorithm and time how long it takes to get an answer. At the end, the thread will output the answer to the screen along with the number of milliseconds it took.

Hint: To find milliseconds just call System.currentTimeMillis$()$; You want to capture this time BEFORE your thread starts searching for the answer then AFTER. What you output is the difference between those two variables. The timing may vary between runs, but with n$=40,$ you should see a pretty large difference.

Attached is an example of my output along with what the $40$th number of the Fibonacci sequence is$.$ Note, it is fine if the dynamic algorithm takes $0$ms$,$ as that means it took less than $1$ ms to complete $($microseconds likely$).$ If your timing is working correctly I would not expect the recursive solution to take less than $1$ms$.$