Achieving mutual recursion without memory issues

Question

I've got two functions set up that I need to continuously call one another (A calls B, which in turn calls A). I understand this isn't possible without causing issues by simply directly calling each function from the other, so I've got a very simple system set up that allows each function to queue the other for execution:

 List<System.Action> toCall = new List<System.Action>();
 
 void Start() {
     toCall.Add(A);
 }
 
 void Update() {
     //  To prevent infinite looping below
     List<System.Action> tempList = new List<System.Action>();
     tempList.AddRange(toCall);
 
     for (int i = 0; i < tempList.Count; i++) {
         toCall.Remove(tempList[i]);
 
         tempList[i]();
     }
 }
 
 void A() {
     toCall.Add(B);
 }
 
 void B() {
     toCall.Add(A);
 }

Unfortunately this system seems to continually use up memory, eventually resulting in a crash, which is exactly what I'm trying to avoid. I'm not super well versed on C#'s memory management, so I may be making a silly oversight here, but any help would still be appreciated.

Answer 1

I don't really see a reason for an outOfMemory exceptions since all memory that is allocated would eventually be garbage collected. So the code you've shown can't be the issue. However you create a lot of garbage which could be avoided. First of all there's no need to recreate your temp list every frame. Currently you create a new list (and an internal array) every frame which will be up for collection after Update. Also AFAIK by passing A or B into the Add method you will actually create a new delegate each time. I'm not 100% sure about that but caching the method delegates would avoid such issues.

 List<System.Action> toCall = new List<System.Action>();
 List<System.Action> tempList = new List<System.Action>();
 System.Action Amethod;
 System.Action Bmethod;
 
 void Start() {
     Amethod = A;
     Bmethod = B;
     toCall.Add(Amethod);
 }
  
 void Update() {
     tempList.AddRange(toCall);
     toCall.Clear();
     for (int i = 0; i < tempList.Count; i++)
         tempList[i]();
     tempList.Clear();
 }
  
 void A() {
     toCall.Add(Bmethod);
 }
 
 void B() {
     toCall.Add(Amethod);
 }

This should only create the additional garbage and no further garbage is generated since we reuse all objects involved.

Keep in mind that if "A" for example adds "B" more than once during one iteration you can still pile up your queued executions endlessly and ultimatively you would run out of memory at some point.

Though without more information about the actual problem you want to solve with your (strange) recursion we can't really help you. Keep in mind that all recursive function can be done iteratively and vice versa. While primitive recursion can be done with just a for loop, any more complex recursion might require a stack anyways since certain information has to carry along. If your problem is not a primitive recursion problem and you want to run it forever it won't work because the deeper you go the more memory you will need regardless if you use plain recursion or your own seperate datastructures. Though implementing an algorithm iteratively with your own memory structures usually allows a much deeper recursion step than using actual recursion. The reason is for actual recursion each method call creates a new stack frame on the stack. The stack is rather small so you can't have too many nested method calls since you will eventually get a stack overflow. Moving the relevant data onto the heap you can use up your total available memory before your algorithm crashes.

Though once again without knowing more about what you're actually doing inside A and B we can't tell you what's wrong or what needs to improved or if it's possible at all.

Achieving mutual recursion without memory issues

1 Reply

Your answer

Follow this Question

Related Questions