$1$

Recursion in Assembly

Programming Lab #$5$

CEG $3310/5310$: Computer Organization

PURPOSE

In this lab you will learn how to implement recursive subroutines in assembly.

ASSIGNMENT

You will be implementing recursive subroutines in assembly. A common exercise in recursive

programming is displaying the Fibonacci Sequence. The Fibonacci sequence is defined as:

F$($n$)=$ F$($n$-1)+$ F$($n$-2)$

Where, F$(0)=0$ and F$(1)=1$

For example, the first $7$ numbers in the Fibonacci Sequence are:

F$(0)$ F$(1)$ F$(2)$ F$(3)$ F$(4)$ F$(5)$ F$(6)$

$0112358$

Notice how F$(2)=$ F$(1)+$ F$(0)=0+1=1$ and how F$(6)=$ F$(5)+$ F$(4)=5+3=8.$

You will have to implement a recursive subroutine that returns the desired number in the Fibonacci

Sequence. An example output of your completed lab should look like the following:

Please enter a number n: $9$

F$(9)=34$

Another example is:

Please enter a number n: $6$

F$(6)=8$

This can be accomplished by implementing a recursive function, with a properly implemented general

and base case. The general case would be F$($n$)=$ F$($n$-1)+$ F$($n$-2)$ and the base cases are F$(0)=0$ and F$(1)=$

$1.$ Notice, in order to calculate F$($n$),$ you must call F$($n$-1)$ and F$($n$-2),$ this will be implemented using

recursion. For a value of n $=3,$ your subroutines will be call each other in this manner:

fibonacci$(3)$ calls fibonacci$(2)+$ fibonacci$(1)$

fibonacci$(2)$ calls fibonacci$(1)+$ fibonacci$(0)$

fibonacci$(1)$ returns $1$ to fibonacci$(2)$ and fibonacci$(3)$

fibonacci$(0)$ returns $0$ to fibonacci$(2)$

fibonacci$(2)$ returns $1+0=1$ to fibonacci$(3)$

fibonacci$(3)$ returns $1+1=2$ to main$()$

main$()$ displays $$F$(3)=2$ to the user

For reference, to implement this in C code, the fibonacci function would look like:

int fibonacci$($int n$)$

$\{$

if$($n $<=1)$

$\{$

return n;

$\}$

else

$\{$

return fibonacci$($n$-1)+$ fibonacci$($n$-2)$;

$\}$

$\}$

IMPLEMENTATION

Write your assembly code in the $$lab$-6.$asm$$ file provided:

$$ Implement the main function in assembly.

$$ Implement the fibonacci function as an LC$3$ assembly subroutine. This function must be

recursive, that is$,$ it calls itself until the base case is reached.

$$ Maintain a proper runtime stack. This runtime stack should allow for multiple fibonacci

subroutine calls, passing inputs to each function call, and returning outputs properly without

losing any data or corrupting data.

GRADING

$$ Main$()$ takes in a user input for the value n

$5$ points

$$ The fibonacci subroutine has a properly implemented general case $($F$($n$)=$ F$($n$-1)+$ F$($n$-2))$

$5$ points

$$ The fibonacci subroutine has properly implemented base cases $($F$(0)=0$ and F$(1)=1)$

$5$ points

$$ The first fibonacci subroutine call returns the correct output to main$()$ from n $=0$ to n $=9$

$5$ points

$$ The runtime stack is properly utilized and the total result of F$($n$)$ is stored in mains return value

location at x$5013$

$5$ points

$$ Your assembly program outputs the Fibonacci sequence number n correctly as formatted below:

Please enter a number n: $9$

F$(9)=34$

$5$ points

$$ Total

$30$ points

For this question i implemented it and got a code but this stucks at the point where i give a number for input

i will give my code here please check and get back to me whether the code is right or not

$.$ORIG x$3000$

; Prompt user for input

LEA R$0,$ PROMPT ; Load address of the prompt message

PUTS ; Display the prompt

GETC ; Read input character from user

OUT ; Output the character $($for confirmation$)$

ADD R$0,$ R$0,$ #$0$ ; Move character to R$0$

; Convert ASCII to integer

LD R$2,$ ASCII$\_$OFFSET ; Load the ASCII offset constant $(48)$

NOT R$2,$ R$2$ ; Compute $-48$

ADD R$2,$ R$2,$ #$1$ ; Complete $2\text{'}$s complement to get $-48$

ADD R$1,$ R$0,$ R$2$ ; Convert ASCII code to integer $($R$0-48)$

; Call Fibonacci subroutine

JSR FIBONACCI

; Store result in memory location x$5013$

LEA R$2,$ RESULT$\_$LOC

STR R$0,$ R$2,$ #$0$

; Display the result

LEA R$0,$ RESULT$\_$MSG ; Load address of result message

PUTS ; Display result message

; Convert result from integer to ASCII

ADD R$0,$ R$0,$ R$2$ ; Convert result from integer to ASCII $($R$0+48)$

OUT ; Output the result

HALT

FIBONACCI

ST R$7,$ SAVE$\_$R$7$ ; Save return address

ST R$1,$ SAVE$\_$R$1$ ; Save R$1($input value$)$

; Base case: if n $==0$

LD R$2,$ ZERO ; Load zero

ADD R$3,$ R$1,$ R$2$ ; Compare input with $0$

BRz BASE$\_$CASE$\_$ZERO

; Base case: if n $==1$

LD R$2,$ ONE ; Load one

ADD R$3,$ R$1,$ R$2$ ; Compare input with $1$

BRz BASE$\_$CASE$\_$ONE

; General case: F$($n$)=$ F$($n$-1)+$ F$($n$-2)$

ADD R$1,$ R$1,$ #$-1$ ; Compute n$-1$

JSR FIBONACCI ; Recursive call for F$($n$-1)$

ADD R$2,$ R$0,$ #$0$ ; Save result of F$($n$-1)$ in R$2$

LD R$1,$ SAVE$\_$R$1$ ; Restore original input value

ADD R$1,$ R$1,$ #$-2$ ; Compute n$-2$

JSR FIBONACCI ; Recursive call for F$($n$-2)$

ADD R$0,$ R$0,$ R$2$ ; Add results of F$($n$-1)$ and F$($n$-2)$