*IN MIPS* Consider the Fibonacci Function, which is defined for any nonnegative
ID: 3589394 • Letter: #
Question
*IN MIPS*
Consider the Fibonacci Function, which is defined for any nonnegative integer n as follows:
Fib(n) = Fib(n-1) + Fib(n-2)
the recursion can be expressed as the following pseudo-code:
int Fib(int n) {
if (n < 0) {
Print "Invalid integer" } else if (n <= 1) {
return n // This base case stops the recursion
} else {
return Fib(n-1) + Fib(n-2)
}
}
write a simple Fibonacci number program in MIPS assembly based on the pseudo-code above.
Your code MUST call itself recursively
Here are two example outputs:
Enter a nonnegative integer: 5
Feb(5) = 5
Enter a nonnegative integer: -2 Invalid integer. Try again. Enter a nonnegative integer: 8 Feb(8) = 21
Explanation / Answer
.LC0:
.string "Invalid integer"
Fib(int):
push rbp
mov rbp, rsp
push rbx
sub rsp, 24
mov DWORD PTR [rbp-20], edi
cmp DWORD PTR [rbp-20], 0
jns .L2
mov edi, OFFSET FLAT:.LC0
mov eax, 0
call printf
jmp .L1
.L2:
cmp DWORD PTR [rbp-20], 1
jg .L4
mov eax, DWORD PTR [rbp-20]
jmp .L1
.L4:
mov eax, DWORD PTR [rbp-20]
sub eax, 1
mov edi, eax
call Fib(int)
mov ebx, eax
mov eax, DWORD PTR [rbp-20]
sub eax, 2
mov edi, eax
call Fib(int)
add eax, ebx
.L1:
add rsp, 24
pop rbx
pop rbp
ret
.LC1:
.string "Enter a non-negative integer"
.LC2:
.string "%d"
main:
push rbp
mov rbp, rsp
sub rsp, 16
mov edi, OFFSET FLAT:.LC1
mov eax, 0
call printf
lea rax, [rbp-4]
mov rsi, rax
mov edi, OFFSET FLAT:.LC2
mov eax, 0
call scanf
mov eax, DWORD PTR [rbp-4]
mov edi, eax
call Fib(int)
mov esi, eax
mov edi, OFFSET FLAT:.LC2
mov eax, 0
call printf
mov eax, 0
leave
ret
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.