Recursion and Sorting in the MIPS Assembly Language



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:



  1. Take some integer as input from the user on run time by using the console of PCSPIM.
  2. Make a factorial procedure and pass the input to it.
  3. Calculate the factorial in a recursive manner.
  4. 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
# integer from the console which the user will enter. It basically implements the “cin” part of the C++

# 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”
# and then prints the result of the factorial which is an integer. It basically implements the “cout” part of
# the C++ Code. Write the code for this part here:

 

 

                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.



Add Comment

Subscribe to our blog to get updates in your email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 1,395 other subscribers