So a little while back, there was some discussion about implementing recursion in TI-BASIC; the entire thread just boiled down to concluding "yeah, even though you can call programs from within programs, there are no return values, so you have to implement your own version of a call stack". All-in-all, recursion is not particularly easy or useful.
But, there are some "exceptions"; take for example this factorial calculator:
Code:
which handles the job quite nicely. It got me wondering if it was possible to accomplish the next step-up in recursive program examples, calculating the Fibonacci sequence, without a call stack or list of some kind; only real variables and Ans.
Well, it turns out you can:
Code:
Why does this work? Well, if you look at the call stack for your average recursive Fibonacci calculator, the number of total calls is actually 2F(n) - 1, for F(n) the nth Fibonacci number. Thus, we don't have to pass return values; just increment some counter every time make a call.
Is this efficient? Absolutely not. Is this adaptable to other recursive problems? Probably not, unless its a slight mathematical modification of the Fibonacci sequence. Is this cool? I think so; I like pushing TI-BASIC.
But, there are some "exceptions"; take for example this factorial calculator:
Code:
value→N:prgmFACT
PROGRAM:FACT
:DS<(N,1:NAns
:If N:prgmFACT
which handles the job quite nicely. It got me wondering if it was possible to accomplish the next step-up in recursive program examples, calculating the Fibonacci sequence, without a call stack or list of some kind; only real variables and Ans.
Well, it turns out you can:
Code:
value→N:0:prmgFIB:.5(Ans+1
PROGRAM:FIB
:DS<(N,1:prgmFIB
:DS<(N,0:prgmFIB
:IS>(N,0::IS>(N,0:
:Ans+1
Why does this work? Well, if you look at the call stack for your average recursive Fibonacci calculator, the number of total calls is actually 2F(n) - 1, for F(n) the nth Fibonacci number. Thus, we don't have to pass return values; just increment some counter every time make a call.
Is this efficient? Absolutely not. Is this adaptable to other recursive problems? Probably not, unless its a slight mathematical modification of the Fibonacci sequence. Is this cool? I think so; I like pushing TI-BASIC.