implement a factorial recursive function in mips
- User
implement a factorial recursive function in mips
- Assistant
Certainly! Below is a MIPS assembly program that implements a recursive factorial function. This program includes a
mainfunction that calls thefactorialfunction with an example input (e.g., 5) and prints the result.Overview
-
Functionality:
main: Initializes the input value, calls thefactorialfunction, and prints the result.factorial: Recursively calculates the factorial of a given number.
-
Key Concepts:
- Recursion: The
factorialfunction calls itself with a decremented value until it reaches the base case. - Stack Management: Saving and restoring registers (
$raand any other used registers) to preserve the program state across recursive calls. - System Calls: Utilizing MIPS system calls to print integers and exit the program.
- Recursion: The
MIPS Assembly Code
# Recursive Factorial in MIPS # This program calculates the factorial of a number using recursion. .data prompt: .asciiz "Factorial Result: " newline: .asciiz "\n" .text .globl main # main function main: # Initialize the input value for factorial li $a0, 5 # Let's calculate 5! as an example jal factorial # Call factorial function move $t0, $v0 # Store the result in $t0 # Print the prompt la $a0, prompt # Load address of prompt string li $v0, 4 # Syscall for print string syscall # Print the factorial result move $a0, $t0 # Move result to $a0 for printing li $v0, 1 # Syscall for print integer syscall # Print a newline la $a0, newline # Load address of newline li $v0, 4 # Syscall for print string syscall # Exit the program li $v0, 10 # Syscall for exit syscall # factorial function: calculates n! recursively # Input: $a0 = n # Output: $v0 = n! factorial: addi $sp, $sp, -8 # Allocate stack space sw $ra, 4($sp) # Save return address sw $a0, 0($sp) # Save current n # Base case: if n <= 1, return 1 li $t1, 1 ble $a0, $t1, base_case # Recursive case: # n! = n * (n-1)! addi $a0, $a0, -1 # Compute n - 1 jal factorial # Recursive call lw $a0, 0($sp) # Restore original n mul $v0, $a0, $v0 # Multiply n * (n-1)! j end_factorial base_case: li $v0, 1 # If n <= 1, return 1 end_factorial: lw $ra, 4($sp) # Restore return address addi $sp, $sp, 8 # Deallocate stack space jr $ra # Return to callerExplanation
-
Data Segment:
prompt: A string to prompt the user before printing the result.newline: A newline character for formatting the output.
-
Text Segment:
-
main:- Initialize Input: Loads the value
5into register$a0, which is the input for the factorial function. - Function Call: Uses
jal factorialto call thefactorialfunction. The result is returned in$v0. - Store Result: Moves the result from
$v0to$t0for temporary storage. - Print Prompt and Result: Uses syscall services to print the prompt and the factorial result.
- Exit: Uses syscall
10to terminate the program.
- Initialize Input: Loads the value
-
factorialFunction:- Stack Management: Allocates space on the stack and saves the return address (
$ra) and the current value of$a0(which holdsn). - Base Case: Checks if
n <= 1. If true, sets$v0to1as0! = 1! = 1. - Recursive Case:
- Decrements
nby1and recursively callsfactorial. - After the recursive call, restores the original
nfrom the stack. - Multiplies
nby the result of(n-1)!to getn!.
- Decrements
- Restore State: Restores the return address and deallocates the stack space before returning to the caller.
- Stack Management: Allocates space on the stack and saves the return address (
-
Running the Program
To assemble and run this MIPS program, you can use the MARS MIPS Simulator or the SPIM Simulator. Here's how you can do it with MARS:
- Assemble: Load the code into MARS and assemble it (usually by clicking the "Assemble" button).
- Run: Execute the program by clicking the "Run" button.
- Output: The console should display:
Factorial Result: 120
This output corresponds to
5! = 120.Notes
-
Registers Used:
$a0-$a3: Argument registers.$v0,$v1: Value registers for function return values.$t0-$t9: Temporary registers.$ra: Return address register.
-
Stack Pointer (
$sp): Used to manage the stack for storing return addresses and local variables during recursion. -
Syscalls:
- 4: Print string.
- 1: Print integer.
- 10: Exit the program.
This recursive implementation efficiently demonstrates how recursion, stack management, and system calls work in MIPS assembly language.
-