# 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