Recursion and Sorting in MIPS Assembly Language

Recursion occurs when a function/procedure calls itself. In this article, we will explore how to calculate the factorial of a number using recursion in MIPS assembly language.

C++ Recursion Example

The C++ code of a program that performs the factorial operation through recursion consists of two parts. The main part of the program takes an integer as input from the user, passes this number to the factorial function, receives the result 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 it reaches the base case. At that point, the nested calls to the factorial procedure start returning.

#include <iostream>
using namespace std;

// Function declaration
int fact(int n);

int main() {
    int x;
    
    // Input from the user
    cout << "Enter a non-negative integer: ";
    cin >> x;
    
    // Calculate and print the factorial
    cout << "Factorial of " << x << " is: " << fact(x) << endl;
    
    return 0;
}

// Recursive factorial function
int fact(int n) {
    if (n < 1) {
        // Do not enter a negative number, return 1 as the base case
        return 1;
    } else {
        // Recursive call to the function itself to calculate factorial
        return n * fact(n - 1);
    }
}

Recursive Factorial in MIPS Assembly Language

To calculate the factorial of a number recursively, we need to follow these steps:

  1. Take some integer as input from the user using the console of PCSPIM.
  2. Create 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.

Below is the MIPS assembly language code to calculate the factorial of a number. Each instruction is provided with a comment for better understanding:

.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:
    # Print the string at Label "Input"
    li $v0, 4
    la $a0, Input
    syscall

    # Read integer from the user
    li $v0, 5
    syscall

    # Pass integer to input argument register $a0
    add $a0, $v0, $zero

    # Function call to the Factorial Function
    jal fact

    # Move factorial result into temp $t0
    add $t0, $v0, $zero

    # Print the string at the Label "Output"
    li $v0, 4
    la $a0, Output
    syscall

    # Move Result to $a0 to print it
    add $a0, $t0, $zero

    # Print the integer result
    li $v0, 1
    syscall

End_Prog:
    # End the program and exit
    li $v0, 10
    syscall

fact:
    # Decrement the stack pointer by 4
    addi $sp, $sp, -4
    sw $ra, 0($sp)  # Push the value of $ra on to the stack

    addi $sp, $sp, -4
    sw $a0, 0($sp)  # Push the value of $a0 on to the stack

    # Check the base condition
    slti $t0, $a0, 1
    beq $t0, $zero, L1  # Branch to Label L1 if base condition not met

    # Put 1 in $v0 as the base condition requires
    addi $v0, $zero, 1

    # Pop the value of $a0 from the stack
    lw $a0, 0($sp)
    addi $sp, $sp, 4  # Increment the stack pointer by 4

    # Pop the value of $ra from the stack
    lw $ra, 0($sp)
    addi $sp, $sp, 4  # Decrement the stack pointer by 4

    jr $ra  # Jump to the address contained in $ra

L1:
    # Base condition not met, perform (n-1)
    addi $a0, $a0, -1

    # Call function fact again with (n-1)
    jal fact

    # Pop the value of $a0 from the stack
    lw $a0, 0($sp)
    addi $sp, $sp, 4  # Increment the stack pointer by 4

    # Pop the value of $ra from the stack
    lw $ra, 0($sp)
    addi $sp, $sp, 4  # Increment the stack pointer by 4

    # Perform multiplication n*fact(n-1)
    mult $a0, $v0

    # Read LO into $v0, assume result fits in 32 bits
    mflo $v0

    jr $ra  # Jump to the address contained in $ra

How this Code Work?

This MIPS assembly code calculates the factorial of a user-entered number using a recursive function. Here’s a detailed explanation of what the code does:

  1. The code begins with a .data section that defines two strings: “Input” and “Output,” which will be used for prompting the user and displaying the result.
  2. In the .text section, the main function is defined as the entry point of the program. It performs the following steps:
    • Prints a message prompting the user to enter a number for which the factorial is to be calculated.
    • Reads an integer input from the user.
    • Calls the fact function to calculate the factorial, passing the input as an argument.
    • Stores the result of the factorial in $t0.
    • Prints a message indicating the result is about to be displayed.
    • Moves the factorial result to $a0 for printing.
    • Prints the integer result.
    • Exits the program.
  3. The fact function is a recursive function that calculates the factorial of a number. It follows these steps:
    • Saves the return address ($ra) and the input argument ($a0) on the stack.
    • Checks if the base condition is met (if the input is less than 1). If met, it returns 1 as the factorial of 0 or a negative number is 1.
    • If the base condition is not met, it decrements the input by 1 and calls itself recursively with the updated input.
    • After the recursive call returns, it performs the multiplication of the current input ($a0) and the result obtained from the recursive call ($v0).
    • It stores the result in $v0 and returns control to the calling function by jumping to the address contained in $ra.

In summary, this code calculates the factorial of a user-entered number using a recursive factorial function. It demonstrates the use of function calls, parameter passing, stack operations for preserving and restoring registers, and conditional branching based on a base condition.

Sorting in MIPS Assembly Language using PCSPIM

In this section, we will explore how to sort an integer array in MIPS assembly language using the bubble sort algorithm.

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 MIPS Assembly Language

Below is the MIPS assembly language code to perform sorting of an integer array. Each instruction is provided with a comment:

.data
Arr:    .word 5, 4, 3, 2, 1

.text
.globl main

main:
    # Pass the base address of the array Arr to input argument register $a0
    la $a0, Arr

    # Pass the value of n=5 to input argument register $a1
    addi $a1, $zero, 5

    # Call the Procedure Sort
    jal sort

End_Prog:
    # Array has been sorted, End the program
    li $v0, 10
    syscall

sort:
    # Push $ra on to the stack
    addi $sp, $sp, -4
    sw $ra, 0($sp)

    # Push $s3 on to the stack
    addi $sp, $sp, -4
    sw $s3, 0($sp)

    # Push $s2 on to the stack
    addi $sp, $sp, -4
    sw $s2, 0($sp)

    # Push $s1 on to the stack
    addi $sp, $sp, -4
    sw $s1, 0($sp)

    # Push $s0 on to the stack
    addi $sp, $sp, -4
    sw $s0, 0($sp)

    # Move base address of Arr to $s2
    add $s2, $a0, $zero

    # Move size of Arr to $s3
    add $s3, $a1, $zero

    # Initialize outer loop index i
    add $s0, $zero, $zero

for_1st:
    # Outer loop check (i < size)
    slt $t0, $s0, $s3
    beq $t0, $zero, exit1

    # Initialize inner loop index j = i-1
    addi $s1, $s0, -1

for_2nd:
    # Inner loop check1 j >= 0
    slti $t0, $s1, 0
    bne $t0, $zero, exit2

    # Place j*4 in $t1 (for Byte Addressing)
    sll $t1, $s1, 2

    # Add j*4 to base address of Arr (Effective Address)
    add $t2, $s2, $t1

    # Load Arr element at Effective Address
    lw $t3, 0($t2)

    # Load Arr element at Effective Address + 4
    lw $t4, 4($t2)

    # Inner loop check2 (Arr[Effective Address] > Arr[Effective Address+4])
    slt $t0, $t4, $t3
    beq $t0, $zero, exit2

    # Move base address of Arr to $a0
    add $a0, $s2, $zero

    # Move current value of inner loop index j to $a1
    add $a1, $s1, $zero

    # Call Procedure Swap
    jal swap

    # Inner loop index j--
    addi $s1, $s1, -1

    j for_2nd  # Jump to the start of the inner loop

exit2:
    # Outer loop index i++
    addi $s0, $s0, 1
    j for_1st  # Jump to the start of the outer loop

exit1:
    # Pop into $s0 from the stack
    lw $s0, 0($sp)
    addi $sp, $sp, 4

    # Pop into $s1 from the stack
    lw $s1, 0($sp)
    addi $sp, $sp, 4

    # Pop into $s2 from the stack
    lw $s2, 0($sp)
    addi $sp, $sp, 4

    # Pop into $s3 from the stack
    lw $s3, 0($sp)
    addi $sp, $sp, 4

    # Pop into $ra from the stack
    lw $ra, 0($sp)
    addi $sp, $sp, 4

    jr $ra  # Return control to caller (Main)

swap:
    # Place index*4 in $t1 (for Byte Addressing)
    sll $t1, $a1, 2

    # Add index*4 to base address of Arr (Effective Address)
    add $t1, $a0, $t1

    # Load Arr[Effective Address] into $t0
    lw $t0, 0($t1)

    # Load Arr[Effective Address + 4] into $t2
    lw $t2, 4($t1)

    # Place contents of $t2 into Arr[Effective Address]
    sw $t2, 0($t1)

    # Place contents of $t0 into Arr[Effective Address + 4]
    sw $t0, 4($t1)

    # Return control to caller (Procedure Sort)
    jr $ra

How Does this Code Work?

This MIPS assembly code is a sorting algorithm that performs an in-place sorting of an array named “Arr.” It uses the Bubble Sort algorithm to sort the array in ascending order. Here’s a detailed explanation of what the code does:

  • The code begins with a .data section that defines an array named “Arr” with initial values. These values will be sorted.
  • The .text section contains the main program labeled as main. It initializes registers $a0 and $a1 with the base address of “Arr” and the size of the array, respectively.
  • It then calls a procedure labeled sort to sort the array.
  • Inside the sort procedure:
    • It saves registers $ra, $s0, $s1, $s2, and $s3 on the stack to preserve their values.
    • It initializes variables, such as $s0 for the outer loop index i, $s1 for the inner loop index j, $s2 for the base address of the array, and $s3 for the size of the array.
    • It enters an outer loop labeled for_1st to iterate through the array.
    • Within the outer loop, there’s an inner loop labeled for_2nd to compare adjacent elements of the array and swap them if necessary, effectively performing a bubble sort.
    • After the sorting is complete, it restores the saved registers and returns control to the caller.
  • Finally, the program exits after sorting the array, and the sorted array prints.

In summary, this code implements the Bubble Sort algorithm to sort an array in ascending order. It demonstrates the use of procedures (sort and swap), nested loops, and stack operations for preserving and restoring registers.

Conclusion

By following the instructions in this article, you can calculate the factorial of a number and perform sorting of an integer array using recursive techniques in MIPS assembly language.

Related content:

Leave a Comment