Рекурсия в MIPS
Я хочу реализовать рекурсивную программу в блоке для MIPS. Строго говоря, я хочу реализовать известную функцию Fibonacci.
Вот реализация в C:
int fib(int n) {
if(n<2)
return 1;
return fib(n-1)+fib(n-2);
}
5 ответов
Вот код для выполнения рекурсивной факториальной функции в сборке MIPS. Замена его на Фибоначчи остаётся читателю в качестве упражнения. (Примечание: слоты задержки не оптимизированы в этом коде, поскольку он разработан для удобства чтения.)
# 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
Скомпилируйте вашу функцию C в объектный файл и посмотрите
objdump -d fib.o
. Может быть вашей отправной точкой.
Подсказка - подумайте о стеке.
Кстати, рекурсия является действительно плохим решением проблемы с точки зрения сложности (как времени, так и пространства). Цикл и две переменные будут работать намного лучше.
Опубликуйте свою попытку, и мы постараемся помочь.
Рекурсия и микро не всегда хорошо сочетаются друг с другом ...
-Загрузить n-1 в $ a0
-Используйте инструкцию jal для вызова fib рекурсивно.
- Получить результат из регистра $ v0 .
-Загрузить n-2 в $ a0
-Используйте инструкцию jal для рекурсивного вызова fib .
- Получить результат из регистра $ v0 .
Затем есть кое-что с инструкцией addu ...
О да, вы должны проверить if с помощью ветки, но это не имеет ничего общего с рекурсией.
Если вам нужна помощь, компилятор - ваш друг.
$ gcc -c -g fib.c
$ objdump -S fib.o
, но
$gcc -S -mrnames fib.c -o fib.s
будет понятнее.