Recursive Functions

So I recently implemented a recursive function in my algo and found some interesting behavior. After implementing the recursive function my algo would complete its calculations with no problem, but the engine would hang on each turn even after the algo submitted it turns.

I want to emphasize that the issue was not a recursive time-out or out of memory bounds. The function completed without issue (very quickly as well) and when I did not call that function the problem went away. I can also confirm that control was given back to the engine.jar (.exe in my case, since I converted it using launch4j).

This began as expected but the engine would gradually hang more and more as each turn finished. This is why I originally believed the issue to be a recursive time-out, but this was not the case when I looked further.

I am wondering why the function would appear to have completed when it clearly has not. The only culprit I could think of was if the engine creates separate threads when running the algos, resulting in it printing my messages, when really the function hasn’t finished. However, this cannot be the case because I set it to output the results of that function, which came back as expected in the time expected and the engine still hung after getting the results.

Furthermore, when I re-wrote the function using an iterative approach, there were no problems at all.

I am wondering if other people have successfully used a recursive function in their algo, any ideas they might have for the problem (for science - since iterative works fine :slight_smile:), or if anyone from C1 has an explanation.

2 Likes

My teammate implemented a recursive function that had the same issue earlier this week. I was trying to debug it and found that it wasn’t hanging, it was just taking quite literally forever. Cutting off the function after its first call would run fine, but by the second, it would take ~50-60 seconds (using the function in approximately 10-20 instances in that time span). What was stranger was the debug messages suggested that the turn ran in under 2 seconds (it was a minute), but I still took full timeout damage. I’ll ask him about it since he ended up resolving it somehow.

I thought it was an implementation problem, but it appears that might not be the case.

Edit: It appears it was an iterated approach that was just implemented incorrectly. The odd behavior with the timing output is unbeknownst to me but the rest was just loops.

1 Like

For those interested/experiencing a similar issue:

The issue I am classifying this as (not a bug) is where nothing prints out but a function (recursive or iterative) may appear to be done. The cause of this is what @Ryan_Draves observed being that a function takes forever. For some reason (I am guessing cpu resources being consumed or sys.stderr being overloaded) this results in zero output even if that function prints to debug_write.

In my specific case, there was a very rare bug that caused infinite loops. The only “strange” thing you may notice is that there is no output even if you print in, before, or after the function.