How would I go about programming the recursive sequence below in QtSpim/MIPS

Question

I am trying to program the following sequence in MIPS/QtSpim:

a(n) = a(n-1) + 2a(n-2)

where a(0) = a(1) = 1

the code should prompt the user to enter the value of n and display the results in the console. I need to use recursion with nested procedure linking to implement the code.

I have tried the following code, but I keep running into errors if I input n as more than 2:

.data
a0: .word 1
a1: .word 1
n: .word 0
an: .word 0

.text
.globl main

main:
    # Prompt user to enter the value of n
    li $v0, 4
    la $a0, prompt
    syscall

    # Read the value of n from the user
    li $v0, 5
    syscall
    move $s0, $v0

    # Call the sequence function
    move $a0, $s0
    jal sequence

    # Display the result
    li $v0, 1
    lw $a0, an
    syscall

    # Exit program
    li $v0, 10
    syscall

sequence:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    beq $a0, 0, a0_case
    beq $a0, 1, a1_case
    addi $a0, $a0, -1
    jal sequence
    lw $t0, an
    addi $a0, $a0, -1
    jal sequence
    lw $t1, an
    add $v0, $t0, $t1
    sll $t1, $t1, 1
    add $t0, $t0, $t1
    sw $t0, an
    j end

a0_case:
    li $v0, 1
    sw $v0, an
    j end

a1_case:
    li $v0, 1
    sw $v0, an

end:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

.data
prompt: .asciiz "Enter the value of n: "

.text

Answer 1

That code doesn't following a calling convention.  Did you want to use the standard calling convention or are you making up your own?

In any case, the registers are mixed up and recursive calling is clobbering values belonging to the recursive callers.  It should go without saying that a CPU register can only hold one value at a time, so, if/when repurposed to hold a different variable, then the previous variable's value is lost.

• $a0 is not a safe place to leave n, the parameter for any given recursive call, because each recursive call modifies that register.  The parameter is needed after the first recursive call in order to make the second such call, but it's been wiped out by the first recursive call.

• $t0 is also not a safe place for temporary data, as it does not survive the second recursive call, since broadly speaking, the function also modifies $t0:

    jal sequence
    lw $t0, an        # t0, assigned here, will be wiped out by the next jal
                      # if the recursion is deep enough
    addi $a0, $a0, -1
    jal sequence
    lw $t1, an
    add $v0, $t0, $t1 # but this code expects it to have a meaningful value 
                      # e.g. as per the above assignment!
                      # but it doesn't since the recursive call 
                      # also used $t0 for its own purposes.

• Using a global variable, an: .word 0 to store the return value from a recursive function is non standard and also error prone (though may work in this particular case).  Return values should be returned just in $v0 alone.  Broadly speaking, global variables are not thread safe, not re-entrant, nor recursion friendly, so use the CPU registers and call stack according to the calling convention instead of globals.

• The following code sequence sets both $v0 and an but to different values.  I don't see $v0 being used anywhere, so there's no point to that add instruction.

     lw $t1, an
     add $v0, $t0, $t1
     sll $t1, $t1, 1
     add $t0, $t0, $t1
     sw $t0, an
     j end

---

So, what you need to do is: (a) provide for and use storage that will survive a function call for n initially in $a0, and also for the temporary result of the first recursive call (Note: already present for $ra).  (b) Remove an global variable and use $v0 exclusively for return values, and (c) fix typos.

---

Let's look at the $ra register, which is being properly used in that code.

What is the $ra register for?  It holds the return address, which is created when a call is made (say via jal).  It is a parameter, hidden from higher level languages, that is supplied to the callee, so that it knows what caller location to return to dynamically, that is, regardless of who did the calling this time.  In older terminology, the return address is called linkage.  If the callee is simple and does not need the $ra register for any other reason, it will leave the caller-provided return address in the $ra register, and use it from there to return to the proper caller — however, if/when the callee also makes a function call, that will necessarily repurpose the $ra register (for this next level of call), whose original value is needed upon eventual return.  So, the approach is to save $ra's entry value to stack local memory — stack local memory survives function calling.  The return address is restored from stack memory in order to return to the caller.  Technically, the value stored in memory doesn't have to be restored to the $ra register, as any register will work as the operand of the jr .. instruction; however, it may help certain hardware with branch prediction if the $ra register is used, and since it is available at the point of return, that is what is commonly done (but the caller does not expect $ra to hold any meaningful value upon return from the call).

so, the $ra register is used in a pattern of storage allocation & original value stored in prologue and restored in epilogue, though the purpose for restoration is so it can be immediately used rather than as benefit for the caller. being returned to.

Your variables n and the temporary for the addition of two function call results, can be handled in the same way.  Allocate sufficient storage for two more words, and initialize one of those words of storage in function prologue from $a0 — this means that the value of n is now both in $a0 and in stack local memory.  You can use the $a0 copy to provide n-1 to the first recursive call.  Leave the other word allocated in prologue uninitialized for now, as it isn't needed until the first recursive call returns.  When the first recursive call completes, store its return value (from $v0) into this other new word of stack local memory, then also reload the original n value from its stack local memory, and compute n-2 for the second recursive call.  When the second recursive call is completed, reload the temporary result of the first call from stack local memory and add it to the $v0 result of the second recursive call, according to your formula.

An astute reader may realize that both saving the original n and the saving of the return value from the first call could actually share the same memory location (reducing stack space usage by the recursion by 1/3), though order of loading of n and saving of $v0 have to be carefully swapped to share that memory location.

Further, I'll point out that the calling convention complexity is the same for any function that makes function calls, whether recursion is involved or not — those rules are all there to make ordinary functions share the fast CPU registers — as long as the system has function call stack, recursion adds no extra rules to the calling convention.

And finally, I'll point out that the standard calling convention is designed to allow one function to call another without the caller knowing implementation details of the callee, without register confliction.  This facilitates separate compilation, as well as function pointers as parameters and in v-tables.

However, a custom calling conventions may improve function calling, when the implementation of both caller and callee can be known in advance, and sometimes assembly programmers and compilers make these modifications.