recursion – I am having a lab about quick sort in ‘RISC-V’. I have done something but my recursive part kept buggy

I guess is stack pointer problem but I can’t fix it. Here is my code:

.global _start
.data
array1: .word -5 24 -8 45 -15 24 11 7 0 125
hi: .word 9
lo: .word 0
newline: .asciz "\n"
space: .asciz " "

.text
_start:
    la s0,array1        #load address of array1[0] in s0
    lw s4,hi        #last elemnt as pivot, pivot index
    lw s5,lo        #start point(lo)
    lw s2,lo        #pivot(p)
    mv t6,s5
    jal partition
    j end
    #call function that loop partition
    
#s2(p),s4(hi),s5(lo),t5(i),t6(j),s3(array1[p])
partition:
    addi sp,sp,-16
    sw ra,0(sp)
    sw s4,4(sp)
    sw s5,8(sp) #store hi,lo,ra
    jal ra,getVal
    mv s3,t0    #the pivot value
    mv s9,s4
    mv s10,s2
    jal ra swap
    mv t6,s5    #cell going to check(j)
    addi t5,t6,-1   #the last cell that elementpivot  
    jal ra,getVal
    ble t0,s3,less  #array1[t6]<=pivot
continue:
    addi t6,t6,1
    j next
        
less:   addi t5,t5,1    #swap array1[j] with array1[i+1]
    mv s10,t6
    mv s9,t5
    jal ra,swap
    j continue

swap:       

#swap array1[k1] and array1[k2] which is store in s9,s10,respectively
    slli t0,s9,2    #store address of array1[k1] in t0
    slli t1,s10,2   #store address of array1[k2] in t1
    add t0,s0,t0    #get address of array1[k1]
    add t1,s0,t1    #address of array1[k2]
    lw t2,0(t0) #t2 store arrary1[k1]
    lw t3,0(t1) #t3 store array1[k2]
    sw t2,0(t1)
    sw t3,0(t0)
    jr ra

getVal:         #get value of cell (array1[t6])
    slli t0,t6,2
    add t0,s0,t0
    lw t0,0(t0)
    jr ra
endPartition:   
    addi t5,t5,1
    sw t5,12(sp)    #store pivot after partition
    mv s10,t5
    mv s9,s4
    jal ra,swap
    jal ra,printArr

    lw s4,4(sp)
    lw s5,8(sp)
    blt s5,s4,recursion
    addi sp,sp,16
    jr ra
recursion:
    lw s2,12(sp)
    addi s4,s2,-1
    lw s5,8(sp)
    mv s2,s5
    mv t6,s5
    jal ra,partition    #recursion for left side
    lw s4,4(sp)
    lw s5,8(sp)
    lw s2,12(sp)
    addi s5,s2,1
    mv s2,s5
    mv t6,s5
    jal ra,partition    #resursion for right side
    jr ra

printArr:
    la t0,array1        #address of array1[0]
    li t1,10        #number of element need to print
printloop:              #loop for printing the array
    beqz,t1,printNewline    #print a newline when all element is print
    lw a0,0(t0)     #print the element
    li a7,1
    ecall
    la a0,space     #print a space as delimiter
    li a7,4
    ecall
    addi t0,t0,4        #move to next elemrnt
    addi t1,t1,-1       #need to print--
    j printloop
printNewline:           #print a newline ready for next sequence
    la a0,newline
    li a7,4
    ecall
    jr ra       #jump back to partitioning

end:

I try drawing a stack graph and figure out after the 4th recursion the sp should go back to -16 (compare with initial). However, it seems that it is at -32? So the become dead-loop.
Initial lo:0,hi:9.
In each partition, I make lo as the initial pivot and swap it with hi.
So in theoretical, after first call the pivot is in 2 which is -5. Then, it recursively call partition again with lo:0,hi,1.
after partition pivot is in 1. It call partition again with lo:0,hi:0.
After this partition, lo>=hi. So it go back to lo:0,hi:1,p:1 and call partition again with lo:2,hi:1.
after this, lo>=hi.so it should go back to lo:0,hi:9,p:2 and call partition with lo:3,hi:9.
But my code start being bug here and enter dead-loop.

Read more here: Source link