CS 21 25.2 Laboratory Exercise 2
Functions in RISC-V
Overview
In our previous lecture, we tackled how to write a function in RISC-V using the proper storing and restoring of RISC-V registers. A function in RISC-V uses registers a0 to a7 for input parameters, while a0 and a1 are used to contain the return values of functions.
The stack frame of RISC-V serves as a memory space for 'scratch' work of functions where values of registers may be temporarily stored and restored using the stack pointer sp to track the top of the stack. It is good practice for all functions in a RISC-V program to have the same rules for storing and restoring register values in the stack. For simplicity, registers whose values may be overwritten or used by a function are usually temporarily stored in the stack frame before executing the function body. The function restores these values prior to returning to the function's caller. Allocation and deallocation is done by moving the sp.
With proper storing and restoring of registers, the implementation of recursive functions is no different from that of nonrecursive functions.
General Instructions
For this laboratory activity, you are to work on one HOPELEx Checkpoint Item that will aid in your understanding of writing RISC-V programs involving functions and recursion.
Important Reminder
You must finish and show your working checkpoint tasks to your lab handler before the end of the laboratory period. HOPELEx checkpoint items contribute 1% to your lab grade.
At the end of the HOPELEx Checkpoints are take-home exercises called TakeHOPE items. These are not graded and will not be submitted, but will help you prepare for the HOPE.
A practice task is provided in the next section to help you warm up prior to the Checkpoint task and be comfortable with writing a simple function in RISC-V. The practice task is not required and will not be checked.
Relevant Links
- Google Classroom (slides, submission bin): https://classroom.google.com/u/2/c/ODQwNDkwODYxODg3
- RISC-V Green Card: https://drive.google.com/file/d/1xSll1ON5cSaOQhoGxpkvr4fKe7lGQFy3/view
Guided Walkthrough
Suppose we are given this C program to convert into RISC-V:
#include <stdio.h>
int g(int n) {
return n * (n - 1);
}
int f(int n) {
printf("%d\n", n);
int k = g(n);
if (n <= 1) {
return k;
} else if (n == 2) {
return 1;
} else {
int ret = k + f(n - 1);
printf("%d\n", n);
return ret;
}
}
int main() {
for (int k = -5; k <= 5; k++) {
printf("f(%d): %d\n", k, f(k));
}
}
Before attempting to convert C code into RISC-V, it is a good idea to refactor the C code such that:
- Each line contains exactly one operation
- Each variable is renamed to include its corresponding register
- Each function call is given the variables
a0,a1, etc. as arguments - Each function argument is saved into another variable that will stay constant
- Each function returns the variable
a0(ideally at the very end) - Each part of all
if-else if-elsechains is turned into its ownif-else - Each nonzero constant used in a condition is placed in its own variable
Optional requirements
The requirements above are entirely optional. You are free to go with a different approach that you are more comfortable with (unless otherwise stated).
Verify that the refactored code below is functionally equivalent to the original C program:
#include <stdio.h>
int g(int a0) {
int n_s0 = a0;
int s1 = n_s0 - 1;
s1 = n_s0 * s1;
a0 = s1;
return a0;
}
int f(int a0) {
int n_s0 = a0;
printf("%d", n_s0);
printf("\n");
a0 = n_s0;
a0 = g(a0);
int k_s1 = a0;
int tmp_s2 = 1;
if (n_s0 <= tmp_s2) {
a0 = k_s1;
return a0;
} else {
tmp_s2 = 2;
if (n_s0 == tmp_s2) {
a0 = 1;
return a0;
} else {
a0 = n_s0 - 1;
a0 = f(a0);
int ret_s3 = k_s1 + a0;
printf("%d", n_s0);
printf("\n");
a0 = ret_s3;
return a0;
}
}
}
int main() {
int k_s0 = -5;
int _5_s2 = 5;
while (k_s0 <= _5_s2) {
int a0 = k_s0;
a0 = f(a0);
int fk_s1 = a0;
printf("f(");
printf("%d", k_s0);
printf("): ");
printf("%d", fk_s1);
printf("\n");
k_s0++;
}
}
Having a C program in this form ensures we (roughly) have a one-to-one correspondence between lines of code in C and RISC-V instructions, turning the remaining steps into a mostly mechanical process.
Let us start with main, taking note of all registers that are modified:
.text
# Modifies s0, s1, s2, a0, a7
main:
li s0, -5 # int k_s0 = -5;
li s2, 5 # int _5_s2 = 5;
main__loop:
bge s2, s0, main__after # while (k_s0 <= _5_s1) {
mv a0, s0 # int a0 = k_s0;
call f # a0 = f(a0);
mv s1, a0 # int fk_s1 = a0;
li a7, 4 # printf("f(");
la a0, str1
ecall
li a7, 1 # printf("%d", k_s0);
mv a0, s0
ecall
li a7, 4 # printf("): ");
la a0, str1
ecall
li a7, 1 # printf("%d", fk_s1);
mv a0, s1
ecall
li a7, 11 # printf("\n");
li a0, 10 # // '\n' == 10
ecall
addi s0, s0, 1 # k_s0++;
j main__loop # }
main__after:
li a7, 10
ecall
.data
str1: .asciz "f("
str2: .asciz "): "
For now, we can define f as a stub (Wikipedia) that prints the argument it is given and returns it just so we can check the correctness of the other parts of our code so far:
.text
# `main` omitted for brevity
# Modifies a7, a0
f: # int f(int a0) {
li a7, 1 # printf("%d");
ecall
li a7, 11 # printf("\n");
li a0, 10
ecall
ret # return a0;
# }
# `.data` omitted for brevity
Verify that the program works as intended stub-wise.
As we are fairly confident that main works as intended at this point, we can now proceed with the mechanical translation of the lines of f.
Tip: Define a unique return label per function
One trick to simplify function conversion is to have only one ret at the end of the function body and to have a label that refers to "the end of the function".
A suggestion for the label name is the function name with the suffix __ret (e.g., f__ret).
Jumping to the label should be synonymous for the function returning the value in a0.
Applying the said tip and doing things step-by-step, we would have the following (note that this is still incorrect):
# `main` omitted for brevity
# Modifies ra, a0, a7, s0, s1, s2
f: # int f(int a0) {
mv s0, a0 # int n_s0 = a0;
li a7, 1 # printf("%d", n_s0);
mv a0, s0
ecall
li a7, 11 # printf("\n");
li a0, 10
ecall
mv a0, s0 # a0 = n_s0;
call g # a0 = g(a0);
mv s1, a0 # int k_s1 = a0;
li s2, 1 # int tmp_s2 = 1;
blt s2, s0, f__else # if (n_s0 <= tmp_s2) {
mv a0, s1 # a0 = k_s1;
j f__ret # return a0;
f__else: # } else {
li s2, 2 # tmp_s2 = 2;
bne s0, s2, f__else_2 # if (n_s0 == tmp_s2) {
li a0, 1 # a0 = 1;
j f__ret # return a0;
f__else_2: # } else {
addi a0, s0, -1 # a0 = n_s0 - 1;
call f # a0 = f(a0);
add s3, s1, a0 # int ret_s3 = k_s1 + a0;
li a7, 1 # printf("%d", n_s0);
mv a0, s0
ecall
li a7, 11 # printf("\n");
li a0, 10
ecall
mv a0, s3 # a0 = ret_s3;
j f__ret # return a0;
# }
# }
# }
f__ret:
ret
# `.data` omitted for brevity
Self-check
The comment says that f modifies ra. Where exactly does f modify ra?
Self-check
Why is the first mv a0, s0 redundant? Why would it still be beneficial to retain it despite the redundancy?
Recall that in RISC-V, registers ("variables") are shared across functions. To help bridge things with C, you may think of all RISC-V registers being global variables in C.
In the scenario that f calls g, f is the caller while g is the callee. You may think of the callee as borrowing all the registers from the caller, and that when the registers are "returned" to the caller, the callee must revert the registers (except a0 and sp) into their old values.
A caller may do this by pushing all the original values of all registers it will be overwriting into stack memory in order to save their values.
Recall that the stack pointer sp points to the top element of the stack, pushing or saving the value of ra may be done as follows:
As a simplification, we adopt the practice that all registers that may be overwritten by a function (except a0 and sp) are pushed into the stack at the very start of the function:
# `main` omitted for brevity
# Modifies ra, a0, a7, s0, s1, s2
# Note: Still incorrect
f: # int f(int a0) {
addi sp, sp, -4 # PUSH ra
sw ra, 0(sp)
addi sp, sp, -4 # PUSH a7
sw ra, 0(sp)
addi sp, sp, -4 # PUSH s0
sw s0, 0(sp)
addi sp, sp, -4 # PUSH s1
sw s1, 0(sp)
addi sp, sp, -4 # PUSH s2
sw s2, 0(sp)
mv s0, a0 # int n_s0 = a0;
li a7, 1 # printf("%d", n_s0);
mv a0, s0
ecall
li a7, 11 # printf("\n");
li a0, 10
ecall
mv a0, s0 # a0 = n_s0;
call g # a0 = g(a0);
mv s1, a0 # int k_s1 = a0;
li s2, 1 # int tmp_s2 = 1;
blt s2, s0, f__else # if (n_s0 <= tmp_s2) {
mv a0, s1 # a0 = k_s1;
j f__ret # return a0;
f__else: # } else {
li s2, 2 # tmp_s2 = 2;
bne s0, s2, f__else_2 # if (n_s0 == tmp_s2) {
li a0, 1 # a0 = 1;
j f__ret # return a0;
f__else_2: # } else {
addi a0, s0, -1 # a0 = n_s0 - 1;
call f # a0 = f(a0);
add s3, s1, a0 # int ret_s3 = k_s1 + a0;
li a7, 1 # printf("%d", n_s0);
mv a0, s0
ecall
li a7, 11 # printf("\n");
li a0, 10
ecall
mv a0, s3 # a0 = ret_s3;
j f__ret # return a0;
# }
# }
# }
f__ret:
ret
# `.data` omitted for brevity
Before a function returns, it must restore the original values of the registers it "borrowed" from its caller.
Notice that the last value pushed by f into the stack is that of s2. It then follows that the top of the stack contains the original value of s2.
If we pop from the stack, we will get the value of s2. Popping this value and placing it in s2 can be done as follows:
Restoring the original values of the registers borrowed by a callee can be done in its return label. We can pop the values we pushed for f and restore them in reverse order (last in, first out):
# `main` omitted for brevity
# Modifies ra, a0, a7, s0, s1, s2
f: # int f(int a0) {
addi sp, sp, -4 # PUSH ra
sw ra, 0(sp)
addi sp, sp, -4 # PUSH a7
sw a7, 0(sp)
addi sp, sp, -4 # PUSH s0
sw s0, 0(sp)
addi sp, sp, -4 # PUSH s1
sw s1, 0(sp)
addi sp, sp, -4 # PUSH s2
sw s2, 0(sp)
mv s0, a0 # int n_s0 = a0;
li a7, 1 # printf("%d", n_s0);
mv a0, s0
ecall
li a7, 11 # printf("\n");
li a0, 10
ecall
mv a0, s0 # a0 = n_s0;
call g # a0 = g(a0);
mv s1, a0 # int k_s1 = a0;
li s2, 1 # int tmp_s2 = 1;
blt s2, s0, f__else # if (n_s0 <= tmp_s2) {
mv a0, s1 # a0 = k_s1;
j f__ret # return a0;
f__else: # } else {
li s2, 2 # tmp_s2 = 2;
bne s0, s2, f__else_2 # if (n_s0 == tmp_s2) {
li a0, 1 # a0 = 1;
j f__ret # return a0;
f__else_2: # } else {
addi a0, s0, -1 # a0 = n_s0 - 1;
call f # a0 = f(a0);
add s3, s1, a0 # int ret_s3 = k_s1 + a0;
li a7, 1 # printf("%d", n_s0);
mv a0, s0
ecall
li a7, 11 # printf("\n");
li a0, 10
ecall
mv a0, s3 # a0 = ret_s3;
j f__ret # return a0;
# }
# }
# }
f__ret:
lw s2, 0(sp) # s2 = POP
addi sp, sp, 4
lw s1, 0(sp) # s1 = POP
addi sp, sp, 4
lw s0, 0(sp) # s0 = POP
addi sp, sp, 4
lw a7, 0(sp) # ra = POP
addi sp, sp, 4
lw ra, 0(sp) # s2 = POP
addi sp, sp, 4
ret
# `.data` omitted for brevity
With f a proper function now, we can continue the mechanical conversion for g:
# `main` and `f` omitted for brevity
# Modifies a0, s0, s1
g: # int g(int a0) {
mv s0, a0 # int n_s0 = a0;
addi s1, s0, -1 # int s1 = n_s0 - 1;
mul s1, s0, s1 # s1 = n_s0 * s1;
mv a0, s1 # a0 = s1;
g__ret:
ret # ret
# }
# `.data` omitted for brevity
We also need to create its stack frame:
# `main` and `f` omitted for brevity
# Modifies s0, s1
g: # int g(int a0) {
addi sp, sp, -4 # PUSH s0
sw s0, 0(sp)
addi sp, sp, -4 # PUSH s1
sw s1, 0(sp)
mv s0, a0 # int n_s0 = a0;
addi s1, s0, -1 # int s1 = n_s0 - 1;
mul s1, s0, s1 # s1 = n_s0 * s1;
mv a0, s1 # a0 = s1;
g__ret:
lw s1, 0(sp) # s1 = POP
addi sp, sp, 4
lw s0, 0(sp) # s0 = POP
addi sp, sp, 4
ret # ret
# }
# `.data` omitted for brevity
Verify that the entire program now works.
Ripes Fork
You are to use a modified version of Ripes accessible via https://ripes.upd-dcs.work.
Local installation may be done by downloading and running the file appropriate for your operating system here: https://github.com/UPD-DCS/Ripes/releases/tag/continuous
This version of Ripes may be executed locally on the DCS TL computers by running ripes on the terminal.
This fork includes a new read integer system call (syscall code 5) that, when invoked, reads a single signed integer input from the user (modulo \(2^{32}\)) and places it in a0.
Practice Task
Convert the following C program into a RISC-V program such that f and g are proper functions (i.e., they have proper stack frames):
int g(int n) {
return n + 2;
}
int f(int n) {
return g(n) + 1;
}
int main() {
int n = f(10);
printf("%d\n", n);
}
HOPELEx Checkpoint
Checkpoint Item: Retain Letters
Expected filename, submission bin
Save your work as lab02checkpoint.s and submit it via the Google Classroom submission bin before the lab session ends.
The following C code takes at most nine printable characters from the user and creates a copy of the input string, but with all non-letter symbols removed:
#include <stdio.h>
char input[10] = {};
char output[10] = {};
void retain_letters(char *p_input, char *p_output, int n) {
if (n <= 0) {
return;
}
char ch = *p_input;
if (ch == '\0') {
return;
} else if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z')) {
*p_output = ch;
p_output++;
}
retain_letters(p_input + 1, p_output, n - 1);
}
int main() {
fgets(input, 10, stdin);
retain_letters(input, output, 10);
printf("%s\n", output);
}
The main function, input, and output have already been converted into RISC-V:
.text
main:
li a7, 63
li a0, 0
la a1, input
li a2, 10
ecall
la a0, input
la a1, output
li a2, 10
call retain_letters
li a7, 4
la a0, output
ecall
li a7, 10
ecall
retain_letters:
# Your code here
.data
input: .zero 11
output: .zero 11
Using this as a template, convert the retain_letters function in C into its recursive RISC-V equivalent.
Restrictions
- You must implement the lab exercise using recursion only (i.e., no loops)
Constraints
- \(0 \le s \le 9\) where \(s\) is the number of printable characters in the input of the user
Test Cases
input |
output |
|---|---|
| (user presses enter immediately) | (empty string) |
Hello! |
Hello |
CS 21 |
CS |
!@#$ |
(empty string) |
kayadapat |
kayadapat |
TakeHOPE Problems
Item 1: Practice Exercises
Item 1a
Consider the following RISC-V program:
.text
main:
li a0, 0x10000000
li t1, 4
li t0, 0
loop:
lw t2, 0(a0)
add t0, t0, t2
addi t2, t2, 2
sw t2, 0(a0)
addi a0, a0, 4
addi t1, t1, -1
bne t1, zero, loop
.data
.word 0x20
.word 0x21
.word 0x140
.word 0x145
- What are the final values of the registers
a0,t0,t1, andt2? - What are the words stored in the following memory addresses?
0x100000000x100000040x100000080x1000000c0x10000010
Item 1b
Consider the following RISC-V program:
.text
main:
la a0, numbers
li a1, 4
li a2, 21
jal ra, start_idx
li a7, 1
ecall
li a7, 10
ecall
start_idx:
li a3, 0
loop:
beq a3, a1, branch_b
lw t0, 0(a0)
beq t0, a2, branch_a
addi a0, a0, 4
addi a3, a3, 1
jal zero, loop
branch_a:
mv a0, a3
jalr zero, ra, 0
branch_b:
li a0, -1
jalr zero, ra, 0
.data
numbers: .word 20, 21, 140, 145
- What does the program do?
- How many iterations of
loopwill occur before the program reaches thebranch_alabel? - What would happen if the line
li a2, 21were to be replaced byli a2, 150? Trace the values ofa0,a1,a2, anda3across each iteration.
Item 1c
Convert the following C program into its RISC-V counterpart (try to do it recursively):
#include <stdio.h>
int length(char *s) {
int len = 0;
while (s[len] != '\0')
len++;
return len;
}
int main(){
char str[] = "Hello, world!!!";
printf("Length of the string: %d\n", length(str));
return 0;
}
Item 1d
Convert the following C function into its RISC-V counterpart:
int count_char(const char *str, char ch) {
if (str == NULL) {
return 0;
}
int count = 0;
for (int i = 0; str[i] != '\0'; i++) {
if (str[i] == ch) {
count++;
}
}
return count;
}
Item 1e
Create a function in RISC-V that capitalizes the letters in a given string. The string must be capitalized in place (i.e. the capitalized string must be found in the same memory location). Also try to obtain the string via user input.
Item 1f
Convert the following C program into a RISC-V program where factorial is still recursive:
int factorial(int n) {
if (n < 0) {
return -21;
} else if (n <= 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
for (int k = -1; k <= 10; k++) {
printf("factorial(%d) = %d\n", k, factorial(n));
}
}
Item 2: Palindrome
A palindrome is a string that is the same when read left-to-right and right-to-left, only considering letters (punctuation, numbers, and other symbols are ignored). Examples are: redivider, Was it a car or a cat I saw?, and A man, a plan, a canal - Panama.
In RISC-V, write a program that does the following in order:
- Within a
mainfunction, get an ASCII string from the user. The string should have a length \(0\leq L\leq 4000 B\). - If the string length is invalid, print
ERROR: STRING LENGTH IS INVALID!before exiting. - Calls a function named
is_palindromethat checks if the input string into a palindrome. The function returns 1 if the input string is a palindrome, and 0 otherwise. Recursion is allowed. - If the input string is a palindrome, print the string in
UPPERCASE. Otherwise, print the string inlowercase. - In either case, exit the program after printing the string.
Item 3: Collatz Conjecture and Hailstone Numbers
The Collatz conjecture is an unsolved (as of 2026 February) problem about the behavior of a very simple algorithm. The algorithm takes a positive integer n and updates its value according to the following two simple rules:
- If n is EVEN, update the value of n by dividing it by 2.
- If n is ODD, update the value of n by multiplying it by 3 then adding 1.
The Collatz conjecture states that for any starting positive integer value of n, iterating the algorithm (i.e. keep updating n using the rules above) will eventually lead to the number having the value 1. The conjecture has been empirically verified for n up to 2.36 sextillion. The sequence of numbers generated by the algorithm (when updating the value of n) is called a hailstone sequence (aka hailstone numbers) since like a hailstone that moves up and down inside a thunderstorm due to updrafts and downdrafts and value of n also moves up (when ODD) and down (when EVEN).
Example Run 1: n = 5
n = 5 is ODD
n = 5*3+1 = 16 is EVEN
n = 16/2 = 8 is EVEN
n = 8/2 = 4 is EVEN
n = 4/2 = 2 is EVEN
n = 2/2 = 1 is ODD
Hailstone Sequence (n = 5):
Example Run 2: n = 22
n = 22 is EVEN
n = 22/2 = 11 is ODD
n = 11*3+1 = 34 is EVEN
n = 34/2 = 17 is ODD
n = 17*3+1 = 52 is EVEN
n = 52/2 = 26 is EVEN
n = 26/2 = 13 is ODD
n = 13*3+1 = 40 is EVEN
n = 40/2 = 20 is EVEN
n = 20/2 = 10 is EVEN
n = 10/2 = 5 is ODD (will continue to run like Example Run 1)
n = 5*3+1 = 16 is EVEN
n = 16/2 = 8 is EVEN
n = 8/2 = 4 is EVEN
n = 4/2 = 2 is EVEN
n = 2/2 = 1 is ODD
Hailstone Sequence (n = 22):
TASK: Create a program in RISC-V assembly that performs the following: 1. Takes an initial value for n (can be hard-coded). 2. Generates the hailstone sequence for the initial value n (stores it in memory, not just printed on the console). 3. Given the hailstone sequence (for n) \(h_0, h_1, h_2, h_3, ..., h_k\) where \(h_0=n\) and \(h_k=1\), it computes $x = (h_0 - h_k) + (h_1 - h_{k-1}) + (h_2 - h_{k-2}) + \cdots + (h_i - h_{k-i}) + \cdots $
Examples:
n = 5
hailstones (n=5): 5, 16, 8, 4, 2, 1
x = (5-1) + (16-2) + (8-4) = 22
n = 22
hailstones (n=22): 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
x = (22-1) + (11-2) + (34-4) + (17-8) + (52-16) + (26-5) + (13-10) + (40-20) = 149
Note: \(x\) can be a negative integer.
For Testing:
| \(n\) | \(x\) |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 19 |
| 4 | 3 |
| 5 | 22 |
| 6 | 9 |
| 7 | 116 |
| 8 | 9 |
| 9 | 101 |
| 10 | 24 |
| 11 | 147 |
| 12 | 5 |
| 13 | 57 |
| 14 | 90 |
| 15 | 482 |
| 16 | 21 |
| 17 | 132 |
| 18 | 93 |
| 19 | 255 |
| 20 | 36 |
| 21 | 118 |
| 22 | 149 |
Item 4: Layers of Stars
The following C code prints a rows of asterisks (*) with decreasing number of columns for each line. Convert the following C program into RISC-V using proper implementation of a function.
#include <stdio.h>
void form_line(int cols) {
if (cols == 0) {
printf("\n");
return;
}
printf("*");
form_line(cols - 1);
}
void layered_stars(int rows, int cols) {
if (rows == 0) {
return;
}
form_line(cols);
layered_stars(rows - 1, cols - 1);
}
int main() {
layered_stars(5, 5);
return 0;
}
Restrictions
- You must implement this using recursion only. No using loops.
Constraints
- $ 0 < rows \le 30$
- \(0 < columns \le 30\)
- \(columns \geq rows\)
Test Cases
Test Case 1: layered_stars(5,5)
Output for Test Case 1
Test Case 2: layered_stars(3,5)
Output for Test Case 2
Test Case 2: layered_stars(1,2)
Output for Test Case 2
Item 5: Recursion vs. Iteration
For the following subitems, consider the RISC-V code below:
.text
main:
la a0, arr
li a1, 6
li a2, 0
call f
li a7, 1
ecall
li a7, 10
ecall
f:
addi sp, sp, -4
sw ra, 0(sp)
addi sp, sp, -4
sw s0, 0(sp)
addi sp, sp, -4
sw s1, 0(sp)
bge zero, a1, f__ret_a2
mv s0, a0
lw s1, 0(s0)
add a2, a2, s1
addi a0, a0, 4
addi a1, a1, -1
call f
j f__ret
f__ret_a2:
mv a0, a2
f__ret:
lw s1, 0(sp)
addi sp, sp, 4
lw s0, 0(sp)
addi sp, sp, 4
lw ra, 0(sp)
addi sp, sp, 4
ret
.data
arr:
.word 10
.word 20
.word 30
.word 40
.word 50
.word 60
Item 5a
Convert the given program into an equivalent C program with a function f that behaves in the way as f in the given RISC-V program (e.g., also recursive, same set of arguments).
Item 5b
Modify f in the given RISC-V program such that it:
- Returns the same output as the original for any given set of inputs (i.e., they are functionally equivalent)
- Is still recursive
- Modifies
sptwice (instead of six times) during each call to it
Item 5c
Modify f in the given RISC-V program such that it:
- Returns the same output as the original for any given set of inputs (i.e., they are functionally equivalent)
- Is not recursive
- Modifies
sptwice (instead of six times) during each call to it
Item 5d
Do the following steps separately for your implementations of f in Item 4b and Item 4c:
- Identify whether
fis recursive - Tabulate the number of instructions of
fthat are executed for thea2values0to10 - Plot the data as a line graph using your graph visualization tool of choice
- Supposing the number of instructions in Step 1 is \(T(n)\) where \(n\) is equal to the value of
a2, express \(T(n)\) using Big \(\mathcal{O}\) notation (e.g., \(T(n) \in \mathcal{O}(n^3)\))
Using the data gathered from the steps above, determine which of your Item 4b and Item 4c implementations of f is faster and explain why the rates of growth of their respective \(T(n)\) functions differ.