# 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

# Function call to the Factorial Function
jal fact

# Move factorial result into temp \$t0

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

# Move Result to \$a0 to print it

# 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
sw \$ra, 0(\$sp)  # Push the value of \$ra on to the stack

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

# 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

L1:
# Base condition not met, perform (n-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

``````

### 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

# 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
sw \$ra, 0(\$sp)

# Push \$s3 on to the stack
sw \$s3, 0(\$sp)

# Push \$s2 on to the stack
sw \$s2, 0(\$sp)

# Push \$s1 on to the stack
sw \$s1, 0(\$sp)

# Push \$s0 on to the stack
sw \$s0, 0(\$sp)

# Move base address of Arr to \$s2

# Move size of Arr to \$s3

# Initialize outer loop index i

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

# Initialize inner loop index j = i-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

lw \$t3, 0(\$t2)

lw \$t4, 4(\$t2)

slt \$t0, \$t4, \$t3
beq \$t0, \$zero, exit2

# Move base address of Arr to \$a0

# Move current value of inner loop index j to \$a1

# Call Procedure Swap
jal swap

# Inner loop index j--

exit2:
# Outer loop index i++

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

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

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

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

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

jr \$ra  # Return control to caller (Main)

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

lw \$t0, 0(\$t1)

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: