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!