MARS (
MIPS Assembler and Runtime Simulator) es un simulador del procesador
MIPS.
El primer paso es escribir la función recursiva que te piden, en este caso:
cuad(n) = n² + cuad(n-1)
cuad(1) = 1
Esa es la
función que debemos implementar (
cuad(n) = n² + cuad(n-1)), y su
caso base (
cuad(1) = 1).
Con esto ya podemos empezar.
Primero, necesitamos saber si se cumple (o no) el caso base (si n = 1), debemos implementar:
Para ello, comprobaremos si
n (el parámetro de entrada
$4)
es menor que 2.
En caso contrario, devolvemos
n (almacenado en
$4), y en caso contrario, saltamos a
else.
Disponemos de la instrucción
slt (Set on Less Than):
Si
$4 (
n),
es menor que 2, el valor de
$8 (registro temporal) será
1, en caso contrario,
0.
Por lo que pasamos a interpretar el valor de retorno con la instrucción
beq (Branch on equal):
Si el contenido de
$8 es igual a 0 (constante en
$0) salta a
else.
Si no, ejecuta la siguiente instrucción.
Ahora queremos devolver
n, es decir, queremos tener en
$2 (registro de salida), lo que haya en
$4 (registro de entrada). Lo podemos solucionar con un simple
add
(
0 + $4 = $4 -> $2)
Y volvemos simplemente con:
(recuerda la instrucción
jal, Jump And Link)
Bien, hasta aquí sencillo.
Ahora hay dos partes, la recursividad, y el cálculo de los valores devueltos.
En primer lugar vamos a implementar la recursividad. Para ello usaremos la
pila (stack).
Recuerda que en
$29 se almacena el puntero (stack pointer), y cómo se almacenan los datos.
Pero, ¿qué debemos almacenar en dicha pila? Muy simple, la dirección de retorno (
$31, por
jal), y el valor calculado en esa etapa (
n²).
Antes, debemos reservar espacio en la pila para estos dos valores:
Restamos 8, 2 palabras (1 palabra = 4 bytes, 2*4 = 8), dejando espacio para dos palabras, siendo
$29 el puntero.
Y calculamos
n²:
Ahora, guardamos en la pila los dos valores, la dirección de retorno (
$31) y
n² (almacenado en
$9):
Nótese el
4 de desplazamiento, ya que el primer valor (
$31) ocupó la primera palabra de las dos que reservamos, la siguiente se deberá almacenar a una distancia de una palabra (4 bytes) del puntero (
$29).
Y ahora llamamos a
cuad(n-1):
Ahora, implementaremos el cálculo de los resultados. Para ello, deberemos retirar de la pila los valores almacenados anteriormente, y seguidamente, efectuar el cálculo de
n² (almacenado en la pila) y el resultado devuelto por
cuad(n-1) (almacenado en
$2).
Ahora sabemos dónde tendremos que ir (
$31) y el valor de
n² (
$4), ya que antes se encontraban en la pila...
Pero no podemos olvidarnos de restaurar la pila para, posteriormente, seguir sacando los valores calculados y las direcciones de salto.
Simplemente, avanzamos el puntero dos palabras hacia delante.
Llegados a este punto, solo nos queda sumar el resultado anterior,
cuad(n-1) (devuelto en
$2) a
n² (almacenado en
$4 ahora), y seguir a la siguiente dirección (almacenada en
$31 ahora):
Como nota final aclaratoria, cabe destacar el uso de
$2 para almacenar el valor del
caso base y para ir guardando los
resultados parciales de la recursividad, y el uso de la pila para almacenar
n², ya que
cuad(n-1) estará disponible en
$2.
Te dejo el código completo.
Código: Seleccionar todo
.data
n: .word 3
.text
main: lw $4, n($0)
jal cuad
li $2, 10
syscall
cuad: slt $8, $4, 2 # n < 2 ?
beq $8, $0, else # j else
add $2, $0, $4 # return n
jr $31
else: addi $29, $29, -8 # reserva 2 posiciones en la pila (2x4 = 8)
mul $9, $4, $4 # n^2
sw $31, 4($29) # guardamos $31 (stack pointer)
sw $9, 0($29) # guardamos n^2
addi $4, $4, -1 # n--
jal cuad # call cuad(n-1)
lw $4, 0($29) # restauramos n^2
lw $31, 4($29) # restauramos $31 (stack pointer)
addi $29, $29, 8 # restauramos la pila
add $2, $4, $2 # return n^2 + cuad(n-1)
jr $31
Cualquier cosa, no dudes en preguntar :D
Un saludo!!