MIPS Assembly Language Programming Exercise: Write a recursive function using a
ID: 3568053 • Letter: M
Question
MIPS Assembly Language Programming Exercise:
Write a recursive function using a stack frame to implement the Fibonacci function, with all parameters passed on the stack, not via registers. Allocate local variables on the stack, not in the data segment. For this exercise, the Fibonacci series is 0, 1, 1, 2, 3, 5, 8 ... and the elements are numbered from 0, so fib(6) = 8.
Your pseudocode for this function will be like this. The parameter n must be held on the stack,
not in a register: The variables x and y are also local variables allocated on the stack.
int Fib( int n )
{
if( n <= 0 )
return 0
endif
if( n == 1 )
return 1
endif
x = Fib( n-1 )
y = Fib( n-2 )
return x + y
}
The return value will be in $v0. You might want to start this by first writing it using a register for the argument, not the stack, and then change it to use the stack. Test up to Fib(10).
I want the code for the recursive function for implementing the Fibonacci function, not the Factorial function.I
Can someone post the Assembly Language code for this problem?
Explanation / Answer
# int fact(int n) fact: subu sp, sp, 32 # Allocate a 32-byte stack frame sw ra, 20(sp) # Save Return Address sw fp, 16(sp) # Save old frame pointer addiu fp, sp, 28 # Setup new frame pointer sw a0, 0(fp) # Save argument (n) to stack lw v0, 0(fp) # Load n into v0 bgtz v0, L2 # if n > 0 jump to rest of the function li v0, 1 # n==1, return 1 j L1 # jump to frame clean-up code L2: lw v1, 0(fp) # Load n into v1 subu v0, v1, 1 # Compute n-1 move a0, v0 # Move n-1 into first argument jal fact # Recursive call lw v1, 0(fp) # Load n into v1 mul v0, v0, v1 # Compute fact(n-1) * n #Result is in v0, so clean up the stack and return L1: lw ra, 20(sp) # Restore return address lw fp, 16(sp) # Restore frame pointer addiu sp, sp, 32 # Pop stack jr ra # return .end fact
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.