Created
October 26, 2012 06:58
-
-
Save b-adams/3957326 to your computer and use it in GitHub Desktop.
CS225 recursive function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ------------------------------------------------------------------------------- | |
| Object | |
| Addr code Symbol Mnemon Operand Comment | |
| ------------------------------------------------------------------------------- | |
| ;Example function with arguments and return value | |
| ;int factorial(int n) | |
| ;finds the nth fibonacci number | |
| ; fibF(0)=fibF(1)=1 | |
| ; fibF(n) = fibF(n-1)+fibF(n-2) | |
| 0000 0400BD BR main | |
| ;FIBONACCI FUNCTION BEGINS | |
| ;Caller's names | |
| FIBUfram:.EQUATE 4 ;Frame size of fibonacci arguments and return value | |
| FIBUn: .EQUATE -4 ;Caller's view of fibFn location | |
| FIBUret: .EQUATE -2 ;Caller's view of fibFret location | |
| ;Callee's names | |
| fibFfram:.EQUATE 4 ;Frame size of fibonacci local variables | |
| fibFn2: .EQUATE 0 ;local variable #2d | |
| fibFn1: .EQUATE 2 ;local variable #2d | |
| fibFretv:.EQUATE 4 ;return address #2h | |
| fibFn: .EQUATE 6 ;formal parameter #2d | |
| fibFret: .EQUATE 8 ;return value #2d | |
| ;Function entry point | |
| 0003 24 fibF: NOP0 | |
| 0004 680004 SUBSP fibFfram,i ;allocate #fibFn1 #fibFn2 | |
| 0007 C30006 LDA fibFn,s ;Load the argument | |
| 000A B00001 CPA 1,i ;Compare to 1: our base cases are for n<=1 | |
| 000D 060013 BRLE fibFBase ;have a 1 (or less), do base case | |
| 0010 04001D BR fibFRec ;have a 2 (or more), do recursive case | |
| 0013 24 fibFBase:NOP0 | |
| 0014 C00001 LDA 1,i | |
| 0017 E30008 STA fibFret,s ;Save the value in the return slot | |
| 001A 04005A BR fibFDone ;finish up with returning stuff | |
| 001D 24 fibFRec: NOP0 | |
| ;Part 1: find fibF(n-1) | |
| 001E C30006 LDA fibFn,s ;Get the argument | |
| 0021 800001 SUBA 1,i ;Find n-1 | |
| 0024 E3FFFC STA FIBUn,s ;Prepare it as an argument | |
| 0027 680004 SUBSP FIBUfram,i ;allocate #fibFret #fibFn | |
| 002A 160003 CALL fibF ;Run fibonacci procedure | |
| 002D 600004 ADDSP FIBUfram,i ;deallocate #fibFn #fibFret | |
| 0030 C3FFFE LDA FIBUret,s ;Get the return value | |
| 0033 E30002 STA fibFn1,s ;Store fibF(n-1) it for future use | |
| ;Part 2: find fibF(n-2) | |
| 0036 C30006 LDA fibFn,s ;Get the argument (again) | |
| 0039 800002 SUBA 2,i ;Find n-2 | |
| 003C E3FFFC STA FIBUn,s ;Prepare it as an argument | |
| 003F 680004 SUBSP FIBUfram,i ;allocate #fibFret #fibFn | |
| 0042 160003 CALL fibF ;Run fibonacci procedure | |
| 0045 600004 ADDSP FIBUfram,i ;deallocate #fibFn #fibFret | |
| 0048 C3FFFE LDA FIBUret,s ;Get the return value | |
| 004B E30000 STA fibFn2,s ;Store fibF(n-2) it for future use | |
| ;Part 3: find their sum and store as return value | |
| 004E C30002 LDA fibFn1,s | |
| 0051 730000 ADDA fibFn2,s | |
| 0054 E30008 STA fibFret,s ;Setting up value as return value | |
| 0057 04005A BR fibFDone ;finish up with returning stuff | |
| 005A 24 fibFDone:NOP0 | |
| 005B 600004 ADDSP fibFfram,i ;deallocate #fibFn2 #fibFn1 | |
| 005E 58 RET0 | |
| ; | |
| ; Entry point for program | |
| ; | |
| 005F 596F75 prompt: .ASCII "You must want a Fibonacci number!\n" | |
| 206D75 | |
| 737420 | |
| 77616E | |
| 742061 | |
| 204669 | |
| 626F6E | |
| 616363 | |
| 69206E | |
| 756D62 | |
| 657221 | |
| 0A | |
| 0081 576869 .ASCII "Which one would you like? \x00" | |
| 636820 | |
| 6F6E65 | |
| 20776F | |
| 756C64 | |
| 20796F | |
| 75206C | |
| 696B65 | |
| 3F2000 | |
| 009C 546865 res1: .ASCII "The \x00" | |
| 2000 | |
| 00A1 746820 res2: .ASCII "th Fibonacci number is...\n\t\x00" | |
| 466962 | |
| 6F6E61 | |
| 636369 | |
| 206E75 | |
| 6D6265 | |
| 722069 | |
| 732E2E | |
| 2E0A09 | |
| 00 | |
| mainfibF:.EQUATE 0 ;local variable #2d | |
| mainin: .EQUATE 2 ;local variable #2d | |
| mainfrm: .EQUATE 4 ;Frame size for main's local variables | |
| 00BD 24 main: NOP0 | |
| 00BE 680004 SUBSP mainfrm,i ;allocate #mainin #mainfibF | |
| 00C1 41005F STRO prompt,d | |
| 00C4 330002 DECI mainin,s ;User input to local variable | |
| 00C7 C30002 LDA mainin,s | |
| 00CA E3FFFC STA FIBUn,s ;Prepare that input as a FIBU argument | |
| 00CD 680004 SUBSP FIBUfram,i ;allocate #fibFret #fibFn | |
| 00D0 160003 CALL fibF ;Run fibonacci procedure | |
| 00D3 600004 ADDSP FIBUfram,i ;deallocate #fibFn #fibFret | |
| 00D6 C3FFFE LDA FIBUret,s ;Get returned value | |
| 00D9 E30000 STA mainfibF,s ;Store returned value | |
| 00DC 41009C STRO res1,d ;The | |
| 00DF 3B0002 DECO mainin,s ;N | |
| 00E2 4100A1 STRO res2,d ;th Fibo is... | |
| 00E5 3B0000 DECO mainfibF,s ;fibF(N) | |
| 00E8 600004 ADDSP mainfrm,i ;deallocate #mainfibF #mainin | |
| 00EB 00 STOP | |
| 00EC .END | |
| ------------------------------------------------------------------------------- | |
| Symbol table | |
| -------------------------------------- | |
| Symbol Value Symbol Value | |
| -------------------------------------- | |
| FIBUfram 0004 FIBUn FFFC | |
| FIBUret FFFE fibF 0003 | |
| fibFBase 0013 fibFDone 005A | |
| fibFRec 001D fibFfram 0004 | |
| fibFn 0006 fibFn1 0002 | |
| fibFn2 0000 fibFret 0008 | |
| fibFretv 0004 main 00BD | |
| mainfibF 0000 mainfrm 0004 | |
| mainin 0002 prompt 005F | |
| res1 009C res2 00A1 | |
| -------------------------------------- |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment