Emulating Recursion on the TI-84+

Yes… it’s true I think about these things in my free time. It actually happened in the middle of a math class I was taking. We were talking about the Fibonacci sequence and I was thinking that it would be neat to have a recursive implementation on my calculator. Now, I know that the iterative approach is actually faster, but the idea of a true recursive implementation was a fun idea. Now, it may be possible using assembly programming for the calculator, but I don’t really know how to do that.

After a little bit of thinking I decided that programming with the calculator BASIC reminded me a bit of MIPS assembly (I can hear some people groan already). You see the calculator lists can be used as a make shift stack and since all the variables A – Z are global you can simply designate one of those as your “stack pointer”. So I adopted the convention that the S variable is the stack pointer and that the R variable is for returning values. Anything else is fair game. I suppose if I really wanted to put thought into this I would pick some of them as temporary and others for function arguments. However I didn’t want to spend that much time working on this.

The basic idea here is that when you want to call a function (IE another program) at the beginning of your function you simply preserve the state of any variables you wish to change by using the list. I happen to use L5, but you could use any list you wanted. The stack pointer starts at 0 and each time you add to the list to increment the stack pointer by the number of items you added. Then at the end of your function you restore the state of any variables you used and “return” by setting the R variable to be the return value.

Now this has some limitations. First of all the TI-BASIC is quite slow even on my 84+ Silver Edition. The second is that a list can only hold 1000 elements so your stack is essentially size 1000. That being said it is still fun to play around with the idea of recursion or the more broad idea of function calls. For instance I wrote a program to do prime factorization which uses a helper program to tell if a number is prime or not.

Here is the code of the main program FIB which is the recursive Fibonacci number finder:

:ClrList L6
:ClrHome
:
:Prompt A
:
:"SET STACK PTR
:1 => S
:
:"GET FIB NUM
:prgmFIBR
:Disp R

Now here is the program which does the real work, FIBR:

:"STOPPING
:"CONDITION
:If A<=2
:Then
:1 => R
:Return
:End
:
:"PUSH VARS
:"ON STACK
:A => L6(S)
:B => L6(S+1)
:T => L6(S+2)
:"Increase stack pointer
:S+3 => S
:
:A => B
:0 => T
:
:"FIBR(n-1)
:A-1 => A
:prgmFIBR
:T+R => T
:
:"FIBR(n-2)
:A-1 => A
:prgmFIBR
:T+R => T
:
:T => R
:
:"POP VARS
:"OFF STACK
:L6(S-3) => A
:L6(S-2) => B
:L6(S-1) => T
:
:"DEC. STACK
:"POINTER
:S-3 => S

If you actually went through the trouble of putting this into your calculator you run the program FIB and enter a positive integer. The program will then return the nth fibanocci number. This is a simple program but I think it gets at the idea of recursion. In any case it doesn’t have too practical a purpose it’s just for fun 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: