**Due: **Check off your implementation of the Recursive Fibonacci in Lab or by 11:59pm on Sunday, March 17th, 2019

In this lab you will re-visit the fibonacci programs that you worked on in P2.

The *Fibonacci sequence* is defined as follows: start
with 0, 1; for the code you are implementing, the zeroth Fibonacci number is
defined to be 0, and the first Fibonacci number is defined to be 1. To
obtain subsequent numbers in the sequence, we take the sum of the previous
two numbers in the sequence. Thus, the second number in the seqeuence is
`0 + 1 = 1`

, and the third number in the sequence is ```
1 + 1
= 2
```

. The function you implement will return the nth Fibonacci number,
where the value `n`

is an input to your function.

There are several ways to compute the Fibonacci sequence. You will implement
the recursive method below. Please **do not** submit
RISC-V code with any form of main function (e.g. instruction that set n to a specific value), we will run it with our own values.

**Recursive Fibonacci:**Simple but inefficient. Logisim would be too slow to use this version except when the index is small.int r_fibonacci(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } return r_fibonacci(n-2) + r_fibonacci(n-1); }

Implement this version of the Fibonacci function using RISC-V assembly code. It must work on the online simulator, though you will have to be careful when testing to select indices whose Fibonacci number can be computed in a reasonable time.

Your Fibonacci function should follow the calling convention covered in
lecture. In particular, it should get its inputs from the argument
registers (`a0`

, `a1`

, etc.) and return its outputs in
the result register `a0`

. If you want to test the function, you can
create a "main" program which initializes the stack (by setting `sp`

and `fp`

to something reasonable and usable) and calls the function
on an input. **If you add testing code to a file, make sure to turn in
a version without the testing code.** Since your function will
follow the calling convention, you'll invoke them from your main program by
loading the input registers, saving caller-saved registers if necessary, and
then executing a `JAL`

instruction.

As a reminder, don't forget to save the previous value in callee-saved registers before you use them in your function!

You can use the following template as your main function, however, you must change the values for the function to work:

addi sp, x0, 1000 addi fp, x0, 1000 addi a0, x0, n //change n to an integer argument jal ra, r_fibonacci jal x0, exit r_fibonacci: // Your function here, starting with the prologue exit:

Recursive fibonacci only uses one argument and doesn't access memory. Binary search takes four arguments and accesses array elements stored in memory. For a bit more challenge, implement the following in RISC-V assembly code.

// Find index of x in arr within the bounds l and r int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l)/2; // How do you divide by two?? if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, l, mid-1, x); return binarySearch(arr, mid+1, r, x); } return -1; } // Convert the following main function to run your code int main(void) { int arr[] = {2, 3, 4, 10, 40}; //Store these values in memory somewhere int n = 5; int x = 10; int result = binarySearch(arr, 0, n-1, x); return result; }