Рекурсия в MIPS

Question

Я хочу реализовать рекурсивную программу в ассемблере для MIPS.Более конкретно, я хочу реализовать хорошо известную функцию Фибоначчи.

Вот реализация в C:

int fib(int n) {
    if(n<2)
        return 1;
    return fib(n-1)+fib(n-2);
}

Answer 1

Вот код для выполнения рекурсивной факториальной функции в сборке 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

Answer 2

-Загрузка 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

будет понятнее.

Answer 3

Подсказка - подумайте о стеке.

Кстати, рекурсия - действительно плохое решение проблемы с точки зрения сложности (как времени, так и пространства).Цикл и две переменные будут работать намного лучше.

Answer 4

Скомпилируйте вашу функцию C в объектный файл и посмотрите на

objdump -d fib.o

Может быть вашей отправной точкой.

Answer 5

Опубликуйте вашу попытку, и мы постараемся помочь.

Хотя рекурсия и микроэффекты не всегда хорошо сочетаются ...