• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 889
  • 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
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

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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