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:

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

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:

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

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

.

- Saves the return address (

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.

- It saves registers
- 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: