Lab 5: Recursive Subroutines

LAB 5: RECURSIVE SUBROUTINESS.R.Norr

OBJECTIVE:

To expose the student to subroutines which call themselves. This emphasizes stack management, the concept of local variables, and the ability to write subroutines without side effects.

DISCUSSION:

Subroutines are commonly “nested”. Nesting implies that within a subroutine, another subroutine is called to execute. A special form of nesting is Recursion. Subroutines, which are recursive (also known as re-entrant), are written to intentionally call themselves as part of the procedure. This is conceptually difficult but can lead to compact and even elegant code. It is important to remember that a recursive program must always have a “way out” of the recursion. For example, a recursive subroutine that calculates the factorial of some number, N, will break out of the recursion when it gets to the point of multiplying by One. N! = N*(N-1)*(N-2) … (2)(1). It is also important to realize that recursive subroutines can only use local variables (data located on the stack). Any absolute referencing will either result in miscalculation or infinite loop. Recursive subroutines must be written so that they do not corrupt any registers, again to avoid miscalculation or misoperation.

PRODECURE:

In this exercise, it is desired to calculate the Nth term of the Fibonocci Sequence. The Fibonocci sequence is (1,1,2,3,5,8,13,21,…..)10. As an example, the 7th term is 13, in decimal. In Hexadecimal, the sequence is (1,1,2,3,5,8,D,15,22,…..)16. Each individual term of the sequence is calculated by adding the two previous terms. Therefore, Fib(N) = Fib(N-1) + Fib(N-2). . In other words, you have to know the two previous Fibonocci terms in order to calculate the desired term. Moreover, in order to know the two previous terms, they must be calculated in the same way (hence the recursion).

Your program should display a prompt for keyboard entry on the Monitor, something like “ENTER TERM:” The program should then look for a valid keypress. Valid numbers will be the hexadecimal range, {3,4,…..,c,d }, so that the output data will fit in one 8-bit register. Any other keypress should display an error message and return to the data entry prompt. As implied, the output will be 1-byte of data.

The Fibonocci number is calculated as follows: Fn = Fn-1 + Fn-2

When your subroutine has calculated the correct number, in HEXADECIMAL (no need to convert to base-10), break it into two nibbles, convert it to ASCII and display it on the Monitor using PutC.

COMMENTS AND ASSUMPTIONS:

You may use the sample code, listed below, as the skeleton of your program. It already does much of what you need to accomplish. This will allow you to concentrate on making the subroutine work correctly.
Initialize your stack pointer at dfff, to maximize the amount of stack at your disposal.
Note that the valid input range starts at term 3. Fib(3) = Fib(2)+Fib(1) = 1+1 = 2
Note that the valid input range ends at D16. This is because Fib(E) > FF16
It should become clear that since Fib(1) = Fib(2) = 1, that your calculation of Fib(N) will differ based on whether N is even or odd.
The best approach may be to consider calling subroutine twice within itself, once for Fib(N-1) and once for Fib(N-2).
Remember that you need a WAY OUT of the recursion. Comment 3 above should provide a clue.
Examine the SumR (RangeSum) recursive subroutine and understand how it works (use the simulator!). The Fibonocci subroutine will not be exotically different.

Good Luck!!

Example Code:

;

; Code for Lab 5 on the EVB

; Must be modified to test on THRSim11

; Program prints a message to screen,

; accepts a keypress, and calculates

; the RangeSum indicated by the key.

;

PutC = bfd3 ;assign labels to the custom

GetC = bfd0 ; instruction address locations

org c000

db 0a,0d,45,4e; Message "Enter Term:"

db 54,45,52,20

db 54,45,52,4d

db 3a,20,00

org c200

Main: lds #dfff ; initialize the stack at bottom of

; memory

cli ; enable interrupts

ldx #c000

Send: ldaa 0,x ; load A with ASCII for Message

beq Wait

psha ; push the contents of A onto the stack

inx

jsr PutC ; Send message to screen

bra Send

Wait: jsr GetC ; use GetC to detect a key press

bcc Wait

pula ; when a key is pressed load the ASCII vale into A

psha ; put it back on the stack

jsr PutC ; dump the ASCII character for the key to the Monitor

ldx #0d0a

pshx ; dump <CR> and <LF> to screen

jsr PutC

cmpa #32 ; check to see if the key press was smaller than 2

blo Inval

cmpa #39

bhi Alph

bra Conv

Alph: cmpa #61

blo Inval

cmpa #66

bhi Inval

Conv: psha

jsr AtoH

jsr SumR

pula

tab

anda #0f

lsrb

psha

jsr HtoA

pshb

jsr HtoA

jsr PutC

bra Main

Inval: ldx #494e ; incorrect keypress branches here

pshx

ldx #414c

pshx

ldx #4944

pshx ; dump "Invalid" to screen

jsr PutC

bra Main ; go back for another keypress

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

SumR:

; A recursive subroutine to calculate RangeSum

; Push number, N, to stack and have the number,

; N + (N-1) + (N-2) + ... + 2 + 1 returned to

; to the stack

; Input: N, a 4-bit unsigned integer, of range

; {1 .le. N .le. F} pushed to stack

; Output: M, an 8-bit result, pushed to stack

; Uses only local variables

pshx

psha

pshb

tsx

ldab 6,x

decb

beq SumOut

pshb

jsr SumR

pulb

ldaa 6,x

aba

staa 6,x

SumOut: pulb

pula

pulx

rts

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

AtoH:

; Convert 8-bit ASCII to 4-bit Hex

; input registers: none - 8-bit

; local variable

; passed to stack

; output registers: none - 8-bit

; local variable

; passed to stack

; 4-bits of leading

; zeros, 4-bits data

;

pshx; store old values of X and A

psha

tsx ; transfer SP contents to X

ldaa 5,x ; load ASCII char from stack

suba #30 ; subtract 30 from ASCII

cmpa #a ; check if number was less than A (10)

blo Done ; if so, done, restore registers

suba #27 ; if not, convert to "a" thru "f" value

Done: staa 5,x ; put HEX number on stack

pula ; restore contents of A and X

pulx

rts

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

HtoA:

; Convert 4-bit Hex to 8-bit ASCII

; input registers: none - 8-bit

; local variable

; passed to stack

; 4-bits of leading

; zeros, 4-bits data

; output registers: none - 8-bit

; local variable

; passed to stack

;

pshx; store old values of X and A

psha

tsx ; transfer SP contents to X

ldaa 5,x ; load ASCII char from stack

adda #30 ; Add 30 to Hex nibble

cmpa #3a ; check if number was less than 3A

blo Done ; if so, done, restore registers

adda #27 ; if not, convert to "a" thru "f" value

Done: staa 5,x ; put ASCII number on stack

pula ; restore contents of A and X

pulx

rts

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;