Correcting the output of "Tower of Hanoi MIPS"

I'm trying to solve the "Tower of Hanoi" problem using MARS MIPS. The output is then written in the file "TOWER_OF_HANOI.txt" with the following format:

Step 1: A=>B
Step 2: A=>C
Step 3: B=>C
...

So far, I have implemented the instruction part for the problem but still struggling with correcting my output. Mine is just:

Step : A=>B
Step : A=>C
...

Here is my implementation:

# Towers of Hanoi
# MIPS assembly implementation (tested with MARS)

.data
prompt: .asciiz "Enter a number: "
part1: .asciiz "\nStage "
part2: .asciiz ": "
part3: .asciiz "==>"
fout:   .asciiz "TOWER_OF_HANOI.txt"      # filename for output
temp: .byte               # store the character A, B, C in the file

.text
.globl main
#########################################################################
# Open (for writing) a file that does not exist
    li   $v0, 13       # system call for open file
    la   $a0, fout     # output file name
    li   $a1, 1        # Open for writing (flags are 0: read, 1: write)
    li   $a2, 0        # mode is ignored
    syscall            # open a file (file descriptor returned in $v0)
    move $s6, $v0      # save the file descriptor 
  
#########################################################################
main:
    li $v0,  4          # print string
        la $a0,  prompt
        syscall
        li $v0,  5          # read integer
        syscall

    # parameters for the routine
        add $a0, $v0, $zero # move to $a0
        li $a1, 'A'
        li $a2, 'B'
        li $a3, 'C'

        jal hanoi           # call hanoi routine
###########################################################
# ?óng file
    li   $v0, 16       # system call for close file
    move $a0, $s6      # file descriptor to close
    syscall            # close file
    
        li $v0, 10          # exit
        syscall
###########################################################
hanoi:

    #save in stack
    addi $sp, $sp, -20 
    sw   $ra, 0($sp)
    sw   $s0, 4($sp)
    sw   $s1, 8($sp)
    sw   $s2, 12($sp)
    sw   $s3, 16($sp)

    add $s0, $a0, $zero
    add $s1, $a1, $zero
    add $s2, $a2, $zero
    add $s3, $a3, $zero

    addi $t1, $zero, 1
    beq $s0, $t1, output

    recur1:

        addi $a0, $s0, -1
        add $a1, $s1, $zero
        add $a2, $s3, $zero
        add $a3, $s2, $zero
        jal hanoi

        j output

    recur2:

        addi $a0, $s0, -1
        add $a1, $s3, $zero
        add $a2, $s2, $zero
        add $a3, $s1, $zero
        jal hanoi

    exithanoi:

        lw   $ra, 0($sp)        # restore registers from stack
        lw   $s0, 4($sp)
        lw   $s1, 8($sp)
        lw   $s2, 12($sp)
        lw   $s3, 16($sp)

        addi $sp, $sp, 20       # restore stack pointer

        jr $ra
##################################################################################3
    output:

        li $v0,  4              # print string
        la $a0,  part1
        syscall
        
          # Write to file just opened
    li   $v0, 15       # system call for write to file
    move $a0, $s6      # file descriptor 
    la   $a1, part1   # address of buffer from which to write
    li   $a2, 5       # hardcoded buffer length
    syscall            # write to file

        
        li $v0,  4              # print string
        la $a0,  part2
        syscall
        
          # Write to file just opened
    li   $v0, 15       # system call for write to file
    move $a0, $s6      # file descriptor 
    la   $a1, part2   # address of buffer from which to write
    li   $a2, 2       # hardcoded buffer length
    syscall            # write to file
        
        li $v0,  11             # print character
        add $a0, $s1, $zero
        sb $a0, temp
        syscall
        
          # Write to file just opened
    li   $v0, 15       # system call for write to file
    move $a0, $s6      # file descriptor 
    la   $a1, temp     # address of buffer from which to write
    li   $a2, 1        # hardcoded buffer length
    syscall            # write to file
       
        li $v0,  4              # print string
        la $a0,  part3
        syscall
        
          # Write to file just opened
    li   $v0, 15       # system call for write to file
    move $a0, $s6      # file descriptor 
    la   $a1, part3   # address of buffer from which to write
    li   $a2, 3       # hardcoded buffer length
    syscall            # write to file
        
        li $v0,  11             # print character
        add $a0, $s2, $zero
        sb $a0, temp
        syscall
        
          # Write to file just opened
    li   $v0, 15       # system call for write to file
    move $a0, $s6      # file descriptor 
    la   $a1, temp     # address of buffer from which to write
    li   $a2, 1       # hardcoded buffer length
    syscall            # write to file

    
    
        beq $s0, $t1, exithanoi
        j recur2

I have 2 approach to this:

1. The first method is something like function passed reference in C/C++. I have tried converting it to MIPS but it didn't work
2. The second one is using a global variable, declared in the .text part or using the register $gp. I have spent hours watching the changes in registers but achieving nothing.

You may use some spare register to keep track of the current iteration number.

li $t7, 0  # Counter

then increment it on every iteration

addiu $t7, $t7, 1 

Keep a buffer to convert this integer to its string representation. So in your data section:

itoa: .asciiz "ITOAITOA"
itoa_end:

and then after writing Stage to the output file convert the integer to string and write it to the file:

# itoa
    la $a1, itoa_end
    addiu $a1, $a1, -1
    li $t6, 10
    li $a2, 0
    move $t5, $t7
itoa_loop:    
    addiu $a1, $a1, -1
    addiu $a2, $a2, 1
    divu $t5, $t6        
    mfhi $t5
    addiu $t5, $t5, '0'
    sb $t5, 0($a1)
    mflo $t5
    bnez $t5, itoa_loop

    li $v0, 15
    move $a0, $s6
    syscall