Help on converting recursive function to iterative

Can anyone help me on converting this function to iterative?
Recursion is too expensive for me, thanks

This is a function to get all child nodes in the parent node.

Code (csharp):

1.  
2. void GetAllNodes(GameObject obj) {
3.         foreach (Transform child in obj.transform) {
4.             GetAllNodes(child.gameObject);
5.         }
6.     }
7.  

 

erm, that isn't a recursive function.... by definition recursive functions call themselves.

 

edited

 

ok... it's also generally a good idea to return a value in recursive functions... but anyway, you were after a way to non recursively find all the children?


gameobject.GetComponentInChildren<Transform>()

http://docs.unity3d.com/ScriptReference/Component.GetComponentInChildren.html

(it's a recursive function itself)



edit: doh, meant the one with the s in it *goes to get coffee*

 

I'm pretty slow.. I dont get where can I use gameobject.GetComponentInChildren<Transform>(), it doesn't return an array of Transform

 

GetComponentsInChildren would return an array of all transforms. GetComponentInChildren returns the first found down the hierarchy.
http://docs.unity3d.com/ScriptReference/Component.GetComponentsInChildren.html

And yes, it too is actually a recursing function.

Though it appears, you're trying to get all children.

Here is a simple recursing example:

Code (csharp):

1.  
2.         public static IEnumerable<Transform> GetAllChildren(this Transform t)
3.         {
4.             //we do the first children first
5.             foreach (Transform trans in t)
6.             {
7.                 yield return trans;
8.             }
9.  
10.             //then grandchildren
11.             foreach (Transform trans in t)
12.             {
13.                 foreach (var child in GetAllChildren(trans))
14.                 {
15.                     yield return child;
16.                 }
17.             }
18.  
19.  
20.         }
21.  

Of course, this is rather intense, and shouldn't be ran frequently. All that garbage... ugh.

As for turning such a function iterative... well that's a rather big task. You're navigating a branching tree, it is structurally recursive. I'm assuming you mean you don't want to have recursive function calls, so as to not use the call stack as the recursion stack.

Thing is, that means you're going to have to create your own stack to recurse down the tree. This could be done with a Stack, or even a List and indexer (the list would be great because you could use it as the return collection as well).

You'd have to push entries into the list, then return back over it to recurse into the members... give me a sec and I'll show you how it'd be done.

 

So it'd look basically like this:

Code (csharp):

1.  
2. public List<Transform> GetAllNodes(Transform obj)
3. {
4.     var lst = new List<Transform>();
5.     for(Transform child in obj)
6.     {
7.         lst.Add(child);
8.     }
9.  
10.     int i = 0;
11.     while(i < lst.Count)
12.     {
13.         obj = lst[i];
14.         for(Transform child in obj)
15.         {
16.             lst.Add(child);
17.         }
18.         i++;
19.     }
20.     return lst;
21. }
22.  

In it we keep adding children to the list. Then we move one spot forward, adding the children of that to the list. It keeps doing so until it reaches the end of the list. Which is only reached when no more children are getting added to the list.

 

Yayy thanks alot!! I got it now lmao.
Quick question, how can I change it so that it will get all the nodes first in a child node instead of an alternating two different nodes?

 

That's doing it recursively.

I mean sure, you could write a way to do it... but doing it as a recursion function would be a LOT more simple. Because you'd basically be simulating the recursion.

Well... you could just insert them into the list at their respective point. This will be expensive though. Probably would be faster to use a linklist to gather them up.

But yeah, if you maintain a second int, j, that instead of 'Add'ing to the list, you 'Insert' at the index just after the current i (i +1 + childIndex), it would result in this.

 

Can I re-name each node based on the parent node they have and just filter them on the List?

 

I would refrain from that, that'd be super slow.

 

Ahh I see. I'm figuring out how to create a similar visual programming to that of scratch XDD

 

What makes you thing an iterative solution will perform any better then a recursive one?

 

Based from the extent of my knowledge, recursion requires more memory(?) because it calls itself.

I'll be using the algorithm on android so I thought, i need to optimize it.
Though i'm not really sure how to do it so I figured converting it..

 

I would profile it before even bothering. You would have to have a very deep hierarchy before this starts to make sense. And if you did have a hierarchy that deep, you would probably gain more by setting up your network in some other way then you will by optimising your recursion.