• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 975
  • Last Modified:

non-recursive fractal tree scripts?

Hi E's

Does anybody know if there is a way to draw a fractal tree without using recursion?

Cheers,
Koza

I have this tree animation, but it's hogging my cpu. I'd like to try to rewrite it using iteration instead of recursion, any ideas?

http://candpgeneration.com/toys/fractal-b.html
0
Kyle Hamilton
Asked:
Kyle Hamilton
  • 4
  • 4
3 Solutions
 
TommySzalapskiCommented:
Yes. You could use a stack. In fact, you can use stacks for basically anything that you can do with recursion.

Every time you would make a recursive call, you just add the data to the stack and go on. You still need to have some stop criteria of course. Then you just loop until the stack is empty.
0
 
Kyle HamiltonData ScientistAuthor Commented:
Let me see if understand... please forgive my programming noobieness :)

Right now, my function has a bunch of arguments. A branch is drawn, and based on the outcome, the arguments are updated, and the function calls itself with the updated arguments. Until the stop criteria.

To use a stack, I would draw a branch, store the resulting data (the updated arguments) in an array and then use the items in the array as arguments on the next iteration of the function?

Am I understaniding this correctly?

Thanks.
0
 
TommySzalapskiCommented:
Yes. An array can easily be used as a stack by only touching the back end of the array to push (add items) and pop (remove items).

So your array would probably get fairly large since each level you add many arguments, but if you used recursion, your call stack would be just as large and the call stack is much more limited than the array can be.

If you want to learn a new tool, there should be a stack type built in to Java. Even just a list would be better than an array because the sizing is more dynamic and you don't need the indexing or memory continuity that you get with arrays.
0
Cloud Class® Course: SQL Server Core 2016

This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

 
Kyle HamiltonData ScientistAuthor Commented:
I'm doing this in javascript, so at least I don't have to worry about the limitations of JAVA arrays, a javascript array is a lot more like and ArrayList.

I re-wrote my script using an array to store the arguments, but I'm missing something because my animation is not the same - it's not drawing all the branches, as you can see below (though my cpu is much happier :))

the original recursive script:
http://candpgeneration.com/arty-farty/fractal-recurse.html

my attempt at using a stack:
http://candpgeneration.com/arty-farty/fractal-iterate.html

I'm not sure I understand the stack thing properly yet.
0
 
TommySzalapskiCommented:
It should look something like this

add first thing to array

while(array not empty)
{
  grab item from end of array (and remove it)
  if(stopCriteria is false)
  {
    for(int i = 0; i < whateverSizeGoesHere; i++)
    {
      add item to end of array;
    }
  }
}

The short story is that you should be adding multiple things to the stack/array at each iteration. It looks like only one thing is getting added.
Every time you would have called the recursive function, you should add something to the array.
0
 
TommySzalapskiCommented:
The reason the recursive stuff wasn't working was because you were running out of call stack. What you are essentially doing is replacing the call stack with your own array (which can be much, much larger). So the structure of the code should be almost identical.
0
 
Kyle HamiltonData ScientistAuthor Commented:
OK. I think I'm slowly starting to get it.. Give me some time. I'll get back to you.

Thanks so much.
0
 
Kyle HamiltonData ScientistAuthor Commented:
Tommy, thanks for all your help. I have some work to do to really understand what I'm doing here. I might post another question when I have something a little more concrete.

Cheers
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Microsoft Windows 7 Basic

This introductory course to Windows 7 environment will teach you about working with the Windows operating system. You will learn about basic functions including start menu; the desktop; managing files, folders, and libraries.

  • 4
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now