Most likely, you already have heard of the Koch curve or seen it. You basically replace the mid of each line with a triangle line.

So I made a Ti Basic Version of it. Since Recursion is not possible in Basic, I programmed my own iterative solution. Basically its just saving all the lines as connection of two points and then it measures the length and angle of each line in the next iteration and inserts the new lines depending on the angle and the length as points. At the end, you can simply run a plot command to graphically show the fractal, since we already saved all the points, which I think is the fastest way to draw it in Ti Basic.
I already posted it on tibasicdev.wikidot.com, but noone could find a good optimization.
Maybe someone here can think of a better method in Ti Basic or optimize my code a bit. (Maybe it is faster using the Lindenmayer system?)
Since my algorithm slows down exponentially each iteration, because the number of points being stored equals 1+4^N at the Nth iteration, it becomes very slow after a few seconds, but the worst problem here is the max dim of a list (999), which limits it to 4 iterations.
I would appreciate you commenting your opinion on that method or suggesting a better method.
Here is the code btw:

Code:


Edit: Oh, and of course I already optimized using the fact that the fractal is symmetrical, meaning you only have to calculate half of the points and then use a mirror algorithm to get the other points (maybe someone knows a better “mirror“ algorithm, I use seq there)

Actually, recursion is quite doable in TI-BASIC using subprograms; check out Chapter 4: Control Structures in Programming the TI-83 Plus/TI-84 Plus if you want more details and a few examples, including a Fibonacci number program. Nevertheless, I'm sufficiently happy that you're familiar with the process of converting an iterative algorithm to a recursive algorithm and vice versa, and applied it correctly here.

I haven't looked at the Koch Snowflake algorithm in much detail before, but is it truly necessary to store the coordinates of the vertices for each iteration? Can those not be computed algorithmically?

Recursion is quite doable in TI-BASIC *without* subprograms, with only logarithmic overhead in the number of subroutines.

Unfortunately, I do not own this book... Of course I know that you are able to create subprograms in Basic, however, local variables are crucial for recursion and since all variables in Basic are global there is no way to pass over a variable in a recursive call of a method.

Yeah, it would be possible, but again it would be slower mainly in terms of drawing since you cannot longer use the Plot#() command if you dont want to save the points. However, thank you for your feedback, I will definetely look into your suggestions. I think, the fractal would look nice if it draws slowly, but has a fast calculation time.


I dont really understand... How would recursion be possible without local variables AND without subprograms?

For basic patterns of recursion, local variables are syntactic sugar over use of a stack which can be pretty trivially implemented with lists. Then you just need a stack pointer to track your recursion depth. To implement calling you need some sort of jump table or subroutine table at the beginning of the program, which can be implemented fairly efficiently (logarithmic overhead) as a binary search, since TI-Basic, to my knowledge, offers no facility for indirected Gotos (which would give O(1) time).

At one point I planned on making a tutorial series out of this sort of thing, but never really got around to it.

Implementing a stack in Basic is indeed possible, but the only downside is how slow accessing it would be. If you get to recursion with 999 iterations, that is going to slow the program down by a ton. But it is definitely doable!

And MasterChief, I give you two big thumbs up for figuring this one out! Basic was probably not the easiest language to figure this out in. looks pretty neat; I just tried it in SC.

Aha, you just reminded me about Doors CS's AnsStack feature. Merthsoft wanted it for recursion related purposes; it essentially provides 10 stacks for local variables of all kinds. Check out a short intro to the AnsStack.

Wow, that is pretty neat! I never even knew that existed! This might actually be very useful for some other ideas i've been bouncing around.

EDIT: Funny, this is exactly how I feel:

Really col, but I wish there was a more efficient way to do this! By the way, using an L-system after n iterations takes 7*4^n entries, so only a couple iterations are feasible :/ However, there is one trick I could think of for reducing memoy cost:

The starting state is F++F++F where F=move forward, +=rotate right 60 degrees, -=rotate left 60 degrees. The replacement is F-F++F-F.

On the very last iteration when you are drawing (from a string, probably) every time you come across an F, instead of moving forward, perform the whole F-F++F-F iteration. So if I read an "F", I would draw a line segment forward, then rotate left, draw a line segment forward, rotate right twice, draw a line segment forward, rotate left, draw a line segment forward. This basically reads each F as an extra iteration, without the cost of multiplying the string size by 4. For better effects, you can store several extra iterations this way!


As to the recursion bit, it is quite possible, you just have to think outside the box!