MIPS Assembly Language Recursion Problems 1. Write a MIPS Assembly Language recu

Question

MIPS Assembly Language Recursion Problems

1. Write a MIPS Assembly Language recursive function that computes the smallest integer in a given array of integers. Use the following algorithm:

int Min(int[] A, int low, int high)

{ if (low == high) return A[low];

int mid = (low + high) / 2;

int min1 = Min(int[] A, low, mid);

int min2 = Min(int[] A, mid + 1, high);

if(min1 > min2) return min2;

return min1;

}

2. Write a MIPS Assembly Language recursive function that compute the Comb(n, r) where n >= r and n, r >= 0

Comb(n, r) = 1 if n = r or r = 0

Comb(n, r) = Comb(n - 1, r) + Comb(n - 1, r - 1)

Explanation / Answer

(2) Solution ::

comb:
sub
$sp, $sp, 16 // move 16 into the stack pointer
sw $ra, 0($sp) // $ra-return the address of current instruction, sw-store word
sw $s1, 4($sp) // stackpointer at location (address) 4
sw $a1, 8($sp) // stackpointer at location (address) 8
sw $a2, 12($sp) // stackpointer at location (address) 12
jal // Instruction that puts the return address into $ra usually the jal instruction.
fact // factorial
move $s1, $v1 // move $v1 into $s1 and store the content at $s1
lw $a1, 12($sp) // load the address of the stack pointer into $a1
jal // Instruction that puts the return address into $ra usually the jal instruction.
fact // factorial
div // division
$s1, $s1, $v1
lw $a1, 8($sp) // load the address of the stack pointer into $a1
lw $a2, 12($sp) // load the address of the stack pointer into $a2
sub
$a1, $a1, $a2
jal // Instruction that puts the return address into $ra usually the jal instruction.
fact // factorial
div // division
$s1, $s1, $v1
move $v1, $s1 // move $s1 into $v1 and store the content at $v1
lw $ra, 0($sp) // load the address of the stack pointer into $ra
lw $s1, 4($sp) // load the address of the stack pointer into $s1
addi $sp, $sp, 16 //add the contents of a register to an immediate value (16) and store the result in a (possibly) another register.
jr $ra //jr $ra jumps to the address in $ra

/// *** Thank You *** ///

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.