Recursion (Factorial) in MIPS assembly language
Recursion occurs when a function/procedure calls itself. Following is the C++ code of a program that performs the factorial operation through recursion. It has two parts. The first part is the main part of the program that takes some integer as the input from the user, passes this number on to the factorial function, gets the result back from the factorial function and displays the result. The second part is the factorial procedure which performs the factorial operation by recursively calling itself until the base case is reached, at which point the nested calls to the factorial procedure start returning.
Recursion example in c language
int main ()
{
int x;
cin >> x;
cout << fact(x);
return 0;
}
int fact (int n)
{
if (n < 1) //Do not enter a negative number
{
return (1); //Base Case
}
else
{
return n*fact(n-1); //Recursive call by the function to itself
}
}
Recursive Factorial in MIPS using pcspim
You are required to do the following:
- Take some integer as input from the user on run time by using the console of PCSPIM.
- Make a factorial procedure and pass the input to it.
- Calculate the factorial in a recursive manner.
- Get the result back in the main part of your program and print it on the console.
MIPS assembly language code to calculate factorial of a number with recursion is given below. Comment is provided with each instruction for better understanding of user.
|
.data Input: .asciiz “\nPlease Enter the number whose factorial is to be calculated: ” Output: .asciiz “\nThe Factorial of the Number is: ”
|
|
.text .globl main main:
|
|
# This part of main takes the input from the user by first printing the string “Input” and then reading an # code. The input value is read into $v0. Write your code for this part here:
li $v0, 4 # Print the String at Label “Input” la $a0, Input syscall li $v0, 5 # Read integer from user syscall
|
|
add $a0, $v0, $zero # Pass integer to input argument register $a0 jal fact # Function call to the Factorial Function. Make sure that the input argument is # passed in the register $a0. Also make sure that fact returns the result in $v0. add $t0, $v0, $zero # Move factorial result into temp $t0
|
|
# This part of the main prints the result of the factorial onto the console. It first prints the string “Output”
li $v0, 4 # Print the String at the Label “Output” la $a0, Output syscall add $a0, $t0, $zero # Move Result to $a0 to Print it li $v0, 1 syscall
|
|
End_Prog: li $v0, 10 # This part of main uses syscall to End the program and exit. Syscall
|
|
fact: # The procedure fact is implemented here. Write its code:
|
| addi $sp, $sp, −4 # Decrement the stack pointer by 4 sw $ra, 0($sp) # Push the value of $ra on to the stack addi $sp, $sp, −4 # Decrement the stack pointer by 4 sw $a0, 0($sp) # Push the value of $a0 on to the stack
slti $t0, $a0, 1 # Check the base condition beq $t0, $zero, L1 # Branch to Label L1 if base condition not met
addi $v0, $zero, 1 # Put 1 in $v0 as the base condition requires
lw $a0, 0($sp) # Pop the value of $a0 from the stack addi $sp, $sp, 4 # Increment the stack pointer by 4 lw $ra, 0($sp) # Pop the value of $ra from the stack addi $sp, $sp, 4 # Decrement the stack pointer by 4
jr $ra # Jump to the address contained in $ra
L1: # Label L1 addi $a0, $a0, −1 # Base condition not met, perform (n-1)
jal fact # Call function fact again with (n-1)
lw $a0, 0($sp) # Pop the value of $a0 from the stack addi $sp, $sp, 4 # Increment the stack pointer by 4 lw $ra, 0($sp) # Pop the value of $ra from the stack addi $sp, $sp, 4 # Increment the stack pointer by 4
mult $a0, $v0 # Perform multiplication n*fact(n-1) mflo $v0 # Read LO into $v0, assume result fits in 32 bits
jr $ra # Jump to the address contained in $ra
|
Type and run this program for the number 7. What is the result: 5040
The first value pushed on to the stack is the value of $ra which contains the return address to the main after the jal fact call in the main, the second value pushed on to the stack is the value in $a0 for the first time which is n = 7, the third value pushed on to the stack is the value of $ra which contains the return address within the fact function after the jal fact call from within fact and the fourth value pushed on to the stack is the value in $a0 after doing (n-1), i.e., 6 for this example.
What is moved into $ra when the function fact is called for the first time and why: 0x00400040 is moved into $ra when the function fact is called for the very first time from the main. It is the value of the return address inside the main after the jal fact instruction. What is moved into $ra when the function fact is called for the second time and why: 0x004000a0 is moved into $ra when the function fact is called from within itself. It is the value of the return address inside the function fact after the jal fact instruction.
The stack grows until the recursion meets the base condition. Until that time, on each function call the value of $a0 is decremented by 1 to perform (n-1) and the function fact is called to perform fact(n-1). Each time the value of $ra and $a0 are pushed on to the stack before performing any other operation. Once the base condition is met, recursive procedure calls start to return with appropriate value in $v0 and on each return the respective values of $a0 and $ra are popped in proper order until we reach the main, thus the stack shrinks. At this time the stack is at its original state from where we started.
SORTING in MIPS assembly language using pcspim
The following C++ Code sorts a given array using the bubble sort algorithm. It is composed of the main part and two functions. The array is defined in the main and the function/procedure sort is called from the main. The procedure sort calls the procedure swap if the elements are not already sorted and so on. (This code has been taken from your text book)
Sorting code in c language
int main ()
{
int v = {5, 4, 3, 2, 1};
int n=5;
sort(v[], n);
return 0;
}
int sort(int v[], int n)
{
int i,j;
for (i=0; i<n; i++)
{
for (j=i-1; j>=0 && v[j] > v[j+1]; j--)
{
swap(v[], j);
}
}
}
int swap(int v[], int k)
{
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
Performing Sorting of an Integer Array in the MIPS Assembly Language
following code for the procedure sort and procedure swap on this work
Code:
|
.data Arr: .word 5, 4, 3, 2, 1
|
|
.text .globl main main: la $a0, Arr # Pass the base address of the array Arr to input argument register $a0 addi $a1, $zero, 5 # Pass the value of n=5 to input argument register $a1 jal sort # Call the Procedure Sort
End_Prog: # Array has been sorted, End the program li $v0, 10 syscall
|
|
sort: # Write the code for the procedure sort here addi $sp, $sp, −4 # Push $ra on to the stack sw $ra, 0($sp) # This is the callee’s responsibility addi $sp, $sp, −4 # Push $s3 on to the stack sw $s3, 0($sp) # This is the callee’s responsibility addi $sp, $sp, −4 # Push $s2 on to the stack sw $s2, 0($sp) # This is the callee’s responsibility addi $sp, $sp, −4 # Push $s1 on to the stack sw $s1, 0($sp) # This is the callee’s responsibility addi $sp, $sp, −4 # Push $s0 on to the stack sw $s0, 0($sp) # This is the callee’s responsibility
add $s2, $a0, $zero # Move base address of Arr to $s2 add $s3, $a1, $zero # Move size of Arr to $s3 add $s0, $zero, $zero # Initialize outer loop index i
for_1st: # Outer For Loop starts here slt $t0, $s0, $s3 # Outer loop check (i<size) beq $t0, $zero, exit1 # Branch to exit1 if i = size of Arr addi $s1, $s0, -1 # Initialize inner loop index j = i-1
for_2nd: slti $t0, $s1, 0 # Inner loop check1 j>=0 bne $t0, $zero, exit2 # Branch to exit2 if j<0
sll $t1, $s1, 2 # Place j*4 in $t1 (for Byte Addressing) add $t2, $s2, $t1 # Add j*4 to base address of Arr (Effective Address) lw $t3, 0($t2) # Load Arr element at Effective Address lw $t4, 4($t2) # Load Arr element at Effective Address + 4
slt $t0, $t4, $t3 # Inner loop check2 (Arr[Effective Address]>Arr[Effective Address+4]) beq $t0, $zero, exit2 # Branch to exit2 if (Arr[Effective Address]<=Arr[Effective Address+4])
add $a0, $s2, $zero # Move base address of Arr to $a0 add $a1, $s1, $zero # Move current value of inner loop index j to $a1
jal swap # Call Procedure Swap
addi $s1, $s1, -1 # Inner loop index j– j for_2nd # Jump to the start of the inner loop
exit2: # This is where inner loop branches when it ends addi $s0, $s0, 1 # Outer loop index i++ j for_1st # Jump to the start of the outer loop
exit1: # This is where outer loop branches when it ends lw $s0, 0($sp) # Pop into $s0 from the stack addi $sp, $sp, 4 # Increment $sp by 4 lw $s1, 0($sp) # Pop into $s1 from the stack addi $sp, $sp, 4 # Increment $sp by 4 lw $s2, 0($sp) # Pop into $s2 from the stack addi $sp, $sp, 4 # Increment $sp by 4 lw $s3, 0($sp) # Pop into $s3 from the stack addi $sp, $sp, 4 # Increment $sp by 4 lw $ra, 0($sp) # Pop into $ra from the stack addi $sp, $sp, 4 # Increment $sp by 4
jr $ra # Return control to caller (Main)
|
|
swap: # code for the procedure swap here
sll $t1, $a1, 2 # Place index*4 in $t1 (for Byte Addressing) add $t1, $a0, $t1 # Add index*4 to base address of Arr (Effective Address) lw $t0, 0($t1) # Load Arr[Effective Address] into $t0 lw $t2, 4($t1) # Load Arr[Effective Address + 4] into $t2 sw $t2, 0($t1) # Place contents of $t2 into Arr[Effective Address] sw $t0, 4($t1) # Place contents of $t0 into Arr[Effective Address + 4] # Thus swap has been performed jr $ra # Return control to caller (Procedure Sort)
|
What is the value of $ra when the procedure sort is called: 0x00400030; address of instruction next to jal sort.What is the value of $ra when the procedure swap is called: 0x004000a4; address of instruction next to jal swap. Apparently there is a conflict of interest here, when the procedure swap is called, the value of $ra that was written when the procedure sort was called, will be lost. How have you resolved this problem? This issue is resolved by pushing the value of $ra (containing the main’s return address) on to the stack at the beginning of the procedure sort. This value is popped from the stack back into $ra at the end of the procedure sort (just before the jr $ra instruction), after control has returned from procedure swap.