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

## Overview

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.

### Testing and input for Fibonacci functions

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 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:
```

### RISC-V (subset) Assembly Syntax

The assembly syntax used by Logisim (and the interpreter) is described at the end of the P2 spec.

### Submitting

When done, submit your RISC-V code to CMS.

### Bonus!

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;
}
```