Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

implement a factorial recursive function in mips

  1. User

    implement a factorial recursive function in mips

  2. Assistant

    Certainly! Below is a MIPS assembly program that implements a recursive factorial function. This program includes a main function that calls the factorial function with an example input (e.g., 5) and prints the result.

    Overview

    1. Functionality:

      • main: Initializes the input value, calls the factorial function, and prints the result.
      • factorial: Recursively calculates the factorial of a given number.
    2. Key Concepts:

      • Recursion: The factorial function calls itself with a decremented value until it reaches the base case.
      • Stack Management: Saving and restoring registers ($ra and 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.

    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 caller
    

    Explanation

    1. Data Segment:

      • prompt: A string to prompt the user before printing the result.
      • newline: A newline character for formatting the output.
    2. Text Segment:

      • main:

        • Initialize Input: Loads the value 5 into register $a0, which is the input for the factorial function.
        • Function Call: Uses jal factorial to call the factorial function. The result is returned in $v0.
        • Store Result: Moves the result from $v0 to $t0 for temporary storage.
        • Print Prompt and Result: Uses syscall services to print the prompt and the factorial result.
        • Exit: Uses syscall 10 to terminate the program.
      • factorial Function:

        • Stack Management: Allocates space on the stack and saves the return address ($ra) and the current value of $a0 (which holds n).
        • Base Case: Checks if n <= 1. If true, sets $v0 to 1 as 0! = 1! = 1.
        • Recursive Case:
          • Decrements n by 1 and recursively calls factorial.
          • After the recursive call, restores the original n from the stack.
          • Multiplies n by the result of (n-1)! to get n!.
        • Restore State: Restores the return address and deallocates the stack space before returning to the caller.

    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:

    1. Assemble: Load the code into MARS and assemble it (usually by clicking the "Assemble" button).
    2. Run: Execute the program by clicking the "Run" button.
    3. 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.