Programming with Ophis
<<< PreviousCall StacksNext >>>

Example: Fibonnacci Numbers

About the simplest "interesting" recursive function is the Fibonacci numbers. The function fib(x) is defined as being 1 if x is 0 or 1, and being fib(x-2)+fib(x-1) otherwise.

Actually expressing it like that directly produces a very inefficient implementation, but it's a simple demonstration of the system. Here's code for expressing the fib function: 

.scope
; Uint16 fib (Uint8 x): compute Xth fibonnaci number.
; fib(0) = fib(1) = 1.
; Stack usage: 3.

fib:    lda     #$03
        jsr     save'stack
        lda     fun'vars
        cmp     #$02
        bcc     _base

        dec     fun'args
        jsr     fib
        lda     fun'args
        sta     fun'vars+1
        lda     fun'args+1
        sta     fun'vars+2
        lda     fun'vars
        sec
        sbc     #$02
        sta     fun'args
        jsr     fib
        clc
        lda     fun'args
        adc     fun'vars+1
        sta     fun'args
        lda     fun'args+1
        adc     fun'vars+2
        sta     fun'args+1
        jmp     _done

_base:  ldy     #$01
        sty     fun'args
        dey
        sty     fun'args+1

_done:  lda     #$03
        jsr     restore'stack
        rts
.scend

The full application, which deals with interfacing with CBM BASIC and handles console I/O and such, is in fibonacci.oph.

<<< PreviousHomeNext >>>
Our GoalsUpExample Programs