Recursividad en MIPS

Question

Deseo implementar un programa recursivo en el ensamblaje para MIPS. Más específicamente, quiero implementar la conocida función de Fibonacci.

Aquí está la aplicación en C:

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

Answer 1

Aquí está el código para hacer una función factorial recursiva en el ensamblaje MIPS. Cambiarlo para hacer Fibonacci se deja como un ejercicio para el lector. (Nota:. Hueco de retardo no están optimizados en este código, ya que está diseñado para facilitar la lectura)

# 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

Publica tu intento y vamos a tratar de ayudar.

Recursión y micro de no siempre juegan bien juntos, aunque ...

Answer 3

compilar su función C en un archivo de objeto y un vistazo a

objdump -d fib.o 

Podría ser su punto de partida.

Answer 4

Sugerencia: piense en una pila.

Por cierto, la recursividad es una muy mala solución al problema en términos de complejidad (tanto de tiempo como de espacio). Un ciclo y dos variables funcionarían mucho mejor.

Answer 5

Load n-1 en $a0

-Utilizar una instrucción jal para llamar fib de forma recursiva.

-Fetch resultado del registro $v0.

Load n-2 en $a0

-Utilizar una instrucción jal para llamar fib de forma recursiva.

-Fetch resultado del registro $v0.

Entonces, hay algo con la instrucción addu ...

Oh sí, usted debe comprobar la if usando una rama, pero eso no tiene nada que ver con la recursividad.

si necesita ayuda, el compilador es su amigo.

$ gcc -c -g fib.c

$ objdump -S fib.o

pero

$gcc -S -mrnames fib.c -o fib.s 

será más clara.