Recursive Program to Find the Sum from 1 to N=10

Write a MIPS recursive function that computes the sum of integers from 1 to N=10 by calling itself with (N-1) and adding N to the result. Use $a0 for the argument, $v0 for the return value, and save $ra on the stack before the call. The base case returns 0 when N is less than or equal to 0.

Understanding Recursive Sum Logic

Recursion solves problems by breaking them into smaller instances of the same problem. For summing numbers from 1 to N, the mathematical definition is straightforward: if N equals 1, the sum is 1; otherwise, it is N plus the sum of numbers from 1 to N-1. In MIPS assembly, this translates to a function that checks a condition, calls itself with a modified argument, and combines the returned value with the current step. The key components are the base case and the recursive step. The base case stops the recursion, preventing infinite loops and stack overflow. For our specific problem where N=10, the recursion depth will be exactly 10 levels. Each level adds its current N to the result returned by the deeper call. This approach mirrors high-level languages like Python or C but requires manual management of the call stack in assembly.

MIPS Register Conventions

Before writing the code, understand how MIPS handles data flow between functions. Registers are categorized into caller-saved and callee-saved registers. When implementing recursion, you must preserve registers that contain important data across function calls.

• $a0-$a3: Argument registers. Pass N here. Since each recursive call needs its own N, these are effectively caller-saved for the next invocation.
• $v0-$v1: Value registers. Return the computed sum here. The caller reads these after the call instruction.
• $ra: Return address. Holds the address to jump back to after the function finishes. This MUST be saved because the recursive call overwrites it.
• $sp: Stack pointer. Points to the top of the stack where local variables and saved registers are stored.

In a recursive function, every time you call the function again, the new instance will overwrite $ra. If you do not save the old $ra on the stack, the program will return to the wrong location upon completion, causing a crash or incorrect behavior.

Implementing the Base Case

The first instruction in your function should check if the recursion should stop. For summing 1 to N, the simplest base case is when N is less than or equal to 0. Alternatively, since we start at 1, checking if N equals 1 is also valid. Use the blt (branch if less than) or beq (branch if equal) instructions. If the condition is met, load 0 into $v0 and jump to the exit label. This avoids further stack operations and immediately begins unwinding the stack.

sum_recursive:
    # Check if N <= 0
    blt $a0, $zero, base_case
    
    # Check if N == 1 (alternative base case)
    li $t0, 1
    beq $a0, $t0, base_case_one

base_case:
    li $v0, 0
    jr $ra

base_case_one:
    li $v0, 1
    jr $ra

While both base cases work, using N <= 0 is more robust for general summation functions that might handle negative inputs or zero. However, for the specific constraint of N=10 starting from positive integers, either works.

Saving State and Making the Recursive Call

If the base case is not met, the function must prepare for the recursive call. First, decrement N by 1 and place it in $a0 for the next call. Then, push $ra onto the stack to preserve the return address for the current frame.

    # Decrement N
    addi $a0, $a0, -1
    
    # Save $ra on stack
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    
    # Recursive call
    jal sum_recursive

After the jal instruction, the program jumps to sum_recursive again. The new instance executes until it hits the base case, then returns via jr $ra. Note that the $ra used here is the one we just saved on the stack.

Restoring State and Combining Results

Once the recursive call returns, the result (the sum of 1 to N-1) is in $v0. You need to add the original N (which was decremented earlier) to this result. To do this, you must restore the original N. Since we modified $a0, we can either save the original N in another register before decrementing or calculate it back. A simpler way is to save the original N on the stack as well, or use a temporary register carefully. However, a cleaner approach is to save the original N before modifying it. Let's refine the sequence:

    # Save original N (in $a0) to temp register or stack
    # Actually, easier: save $ra, then decrement $a0, call, then restore $ra
    
    # After jal returns:
    lw $ra, 0($sp)      # Restore return address
    addi $sp, $sp, 4    # Pop stack
    
    # Now, we need the original N to add to $v0
    # We lost it because we decremented $a0. 
    # Fix: Save original $a0 before decrementing.
    
    # Revised logic inside function:
    # 1. Save $ra
    # 2. Move $a0 to $t0 (save original N)
    # 3. Decrement $a0
    # 4. jal sum_recursive
    # 5. Add $t0 to $v0
    # 6. Restore $ra
    # 7. Return

Here is the complete corrected snippet for the body:

    addi $sp, $sp, -4   # Space for $ra
    sw $ra, 0($sp)
    
    move $t0, $a0       # Save original N in $t0
    addi $a0, $a0, -1   # N = N - 1
    
    jal sum_recursive   # Recursive call
    
    add $v0, $v0, $t0   # Result = (Sum 1 to N-1) + Original N
    
    lw $ra, 0($sp)      # Restore $ra
    addi $sp, $sp, 4    # Restore stack pointer
    jr $ra              # Return

This ensures that after the recursive call returns, $v0 holds the sum of 1 to N-1. Adding the original N (stored in $t0) gives the correct sum for the current level. Finally, restoring $ra and popping the stack allows the caller to continue execution correctly.

Main Program Setup

To test this, write a main program that loads 10 into $a0, calls sum_recursive, and prints the result in $v0. Use syscall 1 for printing integers.

.data
msg: .asciiz "Sum: "

.text
.globl main
main:
    li $a0, 10          # Set N=10
    jal sum_recursive   # Call function
    
    # Print result
    li $v0, 1           # Syscall for print_int
    move $a0, $v0       # Move result to $a0
    syscall
    
    # Exit
    li $v0, 10
    syscall

This structure provides a complete, working example of recursion in MIPS for summing numbers up to 10. It demonstrates proper stack management, register usage, and control flow essential for any recursive algorithm.

Frequently Asked Questions

What happens if I forget to save $ra on the stack?

The program will crash or behave unpredictably because the return address for the current function frame will be overwritten by the recursive call. When the innermost call returns, it will jump to the wrong memory address, likely causing an exception or infinite loop.

Can I use global variables instead of passing N in $a0?

Yes, but it is bad practice for recursive functions. Global variables make the function stateful and non-reentrant, meaning you cannot call it multiple times simultaneously or nest it safely. Passing arguments via registers keeps the function pure and reusable.

Why does the sum start from 1 and not 0?

Adding 0 to a sum does not change the result, so mathematically it is equivalent. However, starting at 1 simplifies the base case logic slightly. If you include 0, your base case must handle 0 explicitly, usually returning 0, which is already covered by the N<=0 check.

How do I debug stack overflow errors in MIPS?

Check your base case to ensure it is reachable and correct. Also, verify that you are decrementing the argument (N) in every recursive step. If N never reaches the base case, the stack grows indefinitely until the simulator runs out of memory.

Is there a performance difference between this and an iterative loop?

Yes, the iterative loop is generally faster and uses less memory because it does not incur the overhead of function calls and stack frame management. Recursion is elegant but adds complexity and resource usage, making it less suitable for very large N values in constrained environments.