;Main Program
; +calls the fib subroutine
;
; Question: If the user enters the digit 9, how many times will we:
;        part a) compute FIB(0)?  (Answer: 21)
;        part b) compute FIB(1)?  (Answer: 34)
;        part c) compute FIB(5)?  (Answer: 5)
;
        .ORIG x3000

;Get digit from user
        LEA R0, BANNER
        TRAP x22        ; Print banner to screen
        TRAP x20        ; Get user input (digit between 0 and 9)
        TRAP x21        ; Echo character to screen
        AND R0, R0, x0F ; Strip ASCII, R0 is now 2's complement 0-9

;Set up stack for recursion
; We will be accessing the stack directly in FIB
; will not check for overflow and underflow!
        LD R6, STACK

;Not checking if input is valid, so be nice!
        JSR FIB         ; R1 = FIB(R0)

;Print Result
        LD R0, LF
        TRAP x21        ; Print a new line
        HALT            ; Answer is in R1
BANNER  .STRINGZ "Enter a digit (0-9): "
LF      .FILL x000D
STACK   .FILL xFE00
;
;
;FIB subroutine
; +Recursive program (i.e., calls itself)
; + FIB(0) = 0
; + FIB(1) = 1
; + FIB(n) = FIB(n-1) + FIB(n-1)
;
; Input is in R0
; Return answer in R1
FIB     ADD R6, R6, #-1
        STR R7, R6, #0  ; Save R7 on the stack
        ADD R6, R6, #-1
        STR R0, R6, #0  ; Save R0 on the stack
        ADD R6, R6, #-1
        STR R2, R6, #0  ; Save R2 on the stack

; Check for base case
        AND R2, R0, #-2
        BRnp SKIP        ; z if R0=0,1
        ADD R1, R0, #0   ; R0 is the answer
        BRnzp DONE

; Not a base case, do the recursion
SKIP    ADD R0, R0, #-1
        JSR FIB         ; R1 = FIB(n-1)
        ADD R2, R1, #0  ; Move result before calling FIB again
        ADD R0, R0, #-1
        JSR FIB         ; R1 = FIB(n-2)
        ADD R1, R2, R1  ; R1 = FIB(n-1) + FIB(n-2)

; Restore registers and return
DONE    LDR R2, R6, #0
        ADD R6, R6, #1
        LDR R0, R6, #0
        ADD R6, R6, #1
        LDR R7, R6, #0
        ADD R6, R6, #1
        RET
.END