Recursive Fibonacci Assembly

Question

i´ve written a code in assembly that recursively calculates the fibonacci sequence for a number. the code is for a RISC V processor. The code works correctly for the numbers 1 and 2 but everything above is not calculated correctly and the registers are written incorrectly. This is my code:

.text
.globl _start
.globl fib       # Export function 'fib'

# Entry point
_start:
    addi a0, x0, 4       # Load 4 into a0
    jal ra, fib          # Jump to fib

fib:
    # Check base cases
    addi t0, x0, 1              # Load 1 into t0
    beq a0, t0, base_case       # If n == 1, jump to base_case
    addi t0, x0, 2              # Load 2 into t0
    beq a0, t0, base_case       # If n == 2, jump to base_case

    # Recursive call for F(n-1)
    addi sp, sp, -4             # Allocate stack space for return address
    sw ra, 0(sp)                # Save return address on the stack
    addi sp, sp, -4             # Allocate stack space for intermediate results
    sw a0, 0(sp)                # Save current value of a0 (n)
    addi a0, a0, -1             # a0 = a0 - 1 (n-1)
    jal ra, fib                 # Call fib(n-1)
    lw t1, 0(sp)                # Load result of F(n-1) into t1
    addi sp, sp, 4              # Restore stack pointer
    lw ra, 0(sp)                # Load return address from the stack
    addi sp, sp, 4              # Restore stack pointer

    # Recursive call for F(n-2)
    addi sp, sp, -4             # Allocate stack space for return address
    sw ra, 0(sp)                # Save return address on the stack
    addi sp, sp, -4             # Allocate stack space for intermediate results
    sw t1, 0(sp)                # Save F(n-1) on the stack
    addi a0, a0, -1             # a0 = a0 - 1 (n-2)
    jal ra, fib                 # Call fib(n-2)
    lw t1, 0(sp)                # Load F(n-1) from the stack into t1
    addi sp, sp, 4              # Restore stack pointer
    lw ra, 0(sp)                # Load return address from the stack
    addi sp, sp, 4              # Restore stack pointer

    # Add results
    add a0, t1, a0              # a0 = t1 + a0 (F(n-1) + F(n-2))
    jalr x0, ra, 0              # Return to the calling function

base_case:
    addi a0, x0, 1              # Base case: result = 1
    jalr x0, ra, 0              # Return to the calling function

The code is designed to calculate F(n) recursively, following the formula F(n) = F(n-1) + F(n-2) . The base cases F(1) = 1 and F(2) = 1 terminate the recursion, while the results are stored in the a0 register.

The stack is used to store return addresses (ra) and intermediate values (a0, t1, t2). Initially, the stack management was inconsistent, leading to incorrect results or corrupted data.

The same register a0 was being used for both input values and results, which led to conflicts and incorrect calculations.

Each jal (jump and link) instruction overwrites the value of ra. If ra is not correctly preserved, the program loses the return address.

The base cases F(1) = 1 and F(2) = 1 were not consistently checked, causing infinite recursion.

Answer 1

Fundamentally, you have two calling convention errors.

While your function is properly returning return values (aka answers) in a0, your function is not expecting them there after the first recursive call!

For example, this line, after the first recursive call:

lw t1, 0(sp)                # Load result of F(n-1) into t1

is both implemented and commented inappropriately, as the result of F(n-1) is already in register a0, not in memory at 0(sp).

What's in 0(sp) is what you stored there before the call, which is n.

The second issue is that you're not obtaining n-2 for the second recursive call.  While n-1 is properly computed and passed to F(n-1) for the first recursive call, when it gets to the second one, register a0 now holds the return value from the first F(n-1) call (neither the original n that was in a0, nor the decremented n as in n-1 for F(n-1)), so you're doing F(F(n-1)) instead of F(n-1), then F(n-2).

---

Your stack handling (pushes and pops) are largely correct; however, not following RISC V standards.  Usually we would allocate a stack frame (once) in prologue and deallocate (once) in epilogue rather than individual pushes & pops as you're doing.

Also, by taking advantage of the offset allowed in loads & stores, you can decrement the stack pointer by 8 in one instruction, then access the two newly allocated slots — one will be at 0(sp) and the other at 4(sp).