Programming - Assembly Stack and Recursive Algorithms

    Hello its'a me again! Today we will continue our talk with functions, but this time we will call functions inside of functions, storing the return address inside of a stack (to don't lose it). I have 3 recursive algorithm codes for you, that use this principle, cause they call themselves again and again... So without further do, let's get started with how we use a Stack and afterwards let's talk about recursive algorithms!


Assembly Stack:

    When calling functions we want to store the $ra register's return value, that contains the position/line in the code that called the function, to don't lose it. Sometimes we even want to store register values, so they don't get lost. To do this Assembly offers a program stack, where we can store those values, so that they don't get lost after calling a new function. 

Stack pointer:

    Assembly offers a register called $sp (stack pointer) that points to a specific memory location of our program, that points at the stack. We will increment/decrease the address value using add/sub instruction, to save/load values inside of it. The logic is opposite and we will have to decrease it to make room for new ones and increment it to delete the old ones. So, this pointer's value has the top of the stack memory when we first start to code, and afterwards we will do calculations on it to store/load values from it.

    To load/store values we will use the same memory instructions we already know, having as parameters the $sp register and an offset. The register value that we always need to save is the one of $ra! The rest ones can be of other registers.

Store values:

For example, if we want to make room for 3 register integer values and afterwards store them into the stack we will use the following code:

 # decrease stack pointer
addi $sp, $sp, -12 # 12/4 = 3 integers
# store values
sw $r1, 0($sp) # store at $sp + 0 address
sw $r2, 4($sp) # store at $sp + 4 address
sw $r3, 8($sp) # store at $sp + 8 address
# never on top of the stack!


Load values:

    To load these values we will use the same logic. This time we first load from each of those locations and afterwards increase the $sp value like that:

# load values
lw $r1, 0($sp) # load from $sp + 0 address
lw $r2, 4($sp) # load from $sp + 4 address
lw $r3, 8($sp) # load from $sp + 8 address
# increase stack pointer
addi $sp, $sp, 12 # 12/4 = 3 integers


Code layout:

    So, our code layout, when we want to call a function inside of a function looks like this:

function1:
# code before calling
# decrease stack to make room for N Bytes
addi $sp, $sp, -N
# store into stack
sw $r1, 0($sp)
sw $r2, 4($sp)
...
sw $r(N-1), (N-4)($sp)
# call function
jal function2
# load from stack
lw $r1, 0($sp)
lw $r2, 4($sp)
...
lw $r(N-1), (N-4)($sp)
# increment stack pointer to previous value
addi $sp, $sp, N
# code after calling
# return to main
jr $ra

Recursive functions:

    Recursive functions, are those that call themselves many times to solve a problem. So, they will be some register values that we will need to store inside of a stack, so they don't get lost when the function calls itself again. We talked about them in C some posts ago. Here you can check it out.

    So, an recursive function needs to store the $ra value and values of registers that get lost when the function calls itself again (like return values). 

    I have 3 example codes for you. The first one is a recursive factorial function, the second one a recursive fibonacci function and the last one a tower of hanoi recursive function.

Code 1(Factorial):

C Code:

int fact(int n)
{
    int f;
    if(n<=0)
        f=1;
    else
        f=n*fact(n-1);
    return f;
}

Assembly Code:

fact:
    addi $sp,$sp, -8 $ space for two words
    sw $ra, 4($sp) #save return address
    sw $ao,0($sp) $temporary variable to hold n

    li $v0, 1
    ble $a0, $zero, fact_return

    addi $a0, $a0, -1
    jal fact
    lw $a0, 0($sp) #retrieve original n
    mul $v0, $v0, $a0 # n*fact(n-1)

    fact_return:
    lw $ra 4($sp) #restore $ra
    addi $sp,$sp, 8 #restore $sp
    jr $ra #back to caller

Code 2(Fibonacci):

C Code:

int fib(int n)
{
    int f;
    if(n<2)
        f=n;
    else
        f=fib(n-1)+fib(n-2)
    return f;
}

Assembly Code:

fib:
 #a0=y
 #if (y==0) return 0;
 #if (y==1) return 1;
 #return( fib(y-1)+fib(y-2) );
 addi $sp,$sp,-12 #save in stack
 sw $ra,0($sp)
 sw $s0,4($sp)
 sw $s1,8($sp)
 
 add $s0,$a0,$zero
 addi $t1,$zero,1
 beq $s0,$zero,return0
 beq $s0,$t1,return1
 
 addi $a0,$s0,-1
 jal fib
 add $s1,$zero,$v0 #s1=fib(y-1)
 
 addi $a0,$s0,-2
 jal fib #v0=fib(n-2)
 add $v0,$v0,$s1 #v0=fib(n-2)+$s1
 
 exitfib:
 lw $ra,0($sp) #read registers from stack
 lw $s0,4($sp)
 lw $s1,8($sp)
 addi $sp,$sp,12 #bring back stack pointer
 jr $ra
 
 return1:
 li $v0,1
 j exitfib
 
 return0 : li $v0,0
 j exitfib


Code 3(Tower of Hanoi):

C Code:

void towers(int num, int frompeg, int topeg, int auxpeg)
{
    if(num == 1)
    {
        printf("\nMove disk 1 from peg %d to peg %d", frompeg, topeg);
        return;
    }
    towers(num - 1, frompeg, auxpeg, topeg);
    printf("\n Move disk %d from peg %d to peg %d, num, frompeg, topeg);
    towers(num -1, auxpeg, topeg, frompeg);
}

Assembly Code:

.text must contain:

disk1_1: .asciiz "\nMove disk 1 from peg "

disk1_2: .asciiz " to peg "

diskx_1: .asciiz "\nMove disk "

diskx_2: .asciiz " from peg "

diskx_3: .asciiz " to peg "

and the function itself is:

towers:
    #decrease stack to store $ra and parameters
    sub $sp,$sp,20
    sw $ra,0($sp)
    sw $a0,4($sp)
    sw $a1,8($sp)
    sw $a2,12($sp)
    sw $a3,16($sp)

    #check if n==1 to do if or notif
    lw $s0,4($sp)
    bne $s0,1,notif
    if:
        # print message for moving disk and return to main
 li $v0,4
 la $a0,disk1_1
 syscall
     
 lw $s1,8($sp)
 li $v0,1
 add $a0,$s1,$0
 syscall
     
 li $v0,4
 la $a0,disk1_2
 syscall
     
 lw $s2,12($sp)
 li $v0,1
 add $a0,$s2,$0
 syscall
     
 lw $ra,0($sp)
 add $sp,$sp,20
 jr $ra  
 
    notif:
        #call towers with swapped parameters (aux and to)
 lw $s0,4($sp)
 sub $s0,$s0,1
 move $a0,$s0
 lw $s1,8($sp)
 move $a1,$s1
 lw $s3,16($sp)
 move $a2,$s3
 lw $s2,12($sp)
 move $a3,$s2    
 jal towers
     
         #print message for moving disk
 li $v0,4
 la $a0,diskx_1
 syscall
     
 lw $s0,4($sp)
 li $v0,1
 move $a0,$s0
 syscall
     
 li $v0,4
 la $a0,diskx_2
 syscall
         
 lw $s1,8($sp)
 li $v0,1
 move $a0,$s1
 syscall
     
 li $v0,4
 la $a0,diskx_3
 syscall
     
 lw $s2,12($sp)
 li $v0,1
 move $a0,$s2
 syscall
     
        #call towers with swapped parameters (aux and from)
 lw $s0,4($sp)
 sub $s0,$s0,1
 move $a0,$s0
 lw $s3,16($sp)
 move $a1,$s3
 lw $s2,12($sp)
 move $a2,$s2
 lw $s1,8($sp)
 move $a3,$s1
 jal towers
 
 lw $ra,0($sp)
 add $sp,$sp,20
 jr $ra  


    This is the end of today's post! Hope you learned something new and enjoyed it. We are finished with the most stuff that I wanted to show you! Only some little things remain and I will then upload more advanced codes from time to time! 

    Next post will be about Dynamic Memory Allocation and we will create an real dynamic array (and not an pseudodynamic like last time)!

Until next time...Bye!

H2
H3
H4
3 columns
2 columns
1 column
Join the conversation now