• Hello [name]! Thanks for joining the GMC. Before making any posts in the Tech Support forum, can we suggest you read the forum rules? These are simple guidelines that we ask you to follow so that you can get the best help possible for your issue.

Question - Code recursion

A

anomalous

Guest
I ran a flood fill this morning recursively and it appeared to run fine in small runs, but in a larger size it caused game maker to stop working. Is recursive still an issue/to be avoided?

The larger run was only about a 20x20 grid, while it ran on about 10x10 I think. Just guessing, it was not huge.

I converted to a stack and it ran fine, but much slower unfortunately. Is recursion bad practice in general?
 

csanyk

Member
I ran a flood fill this morning recursively and it appeared to run fine in small runs, but in a larger size it caused game maker to stop working. Is recursive still an issue/to be avoided?

The larger run was only about a 20x20 grid, while it ran on about 10x10 I think. Just guessing, it was not huge.

I converted to a stack and it ran fine, but much slower unfortunately. Is recursion bad practice in general?
Recursion is always tricky. The key is you need to efficiently reduce the problem with each call of the recursion loop. You need to ensure that the algorithm you're using always and necessarily does this each time the function calls itself.
The biggest problem with recursion, in GameMaker, is that given that recursion is essentially a looping structure, and loops will slow down fps if they're not efficient.

Recursive scripts can also get out of control with how much memory they consume.

It can be more manageable if you can get your recursive function to call itself only once per step, or N iterations per step, where N is small enough not to kill performance, until it resolves.
 
N

NPT

Guest
Historically GameMaker has had a problem with the number of levels that one can recurse.

The problems in the past has been not enough levels. But I seem to recall GM throwing an error nor just crashing.

I would write the app in GM 1.4 and 2 and compare behaviours, I would also display the levels deep to see if there is consistancy at the level it crashes.

In either event it should throw an error and not just crash, therefore you probablt want to report a bug.
 

FrostyCat

Member
Are you calling the fill script straight or through script_execute()? And is the grid a genuine grid or 2D array, or just an arrangement of instances? The latter option in both cases are the inferior rookie-preferred picks that have performance issues and may blow the stack early.
 

YellowAfterlife

ᴏɴʟɪɴᴇ ᴍᴜʟᴛɪᴘʟᴀʏᴇʀ
Forum Staff
Moderator
An extra thing to keep in mind is that on YYC you're put under the limits of C++ stack depth rather than those of GML VM.

Ideally the algorithms should be programmed to manage their own stack/queue/priority list (as a memory structure) rather than relying on system-specific features.
 
A

anomalous

Guest
Thanks for the input. I'll check again at some point, and if it still crashes I'll submit a bug report. What started this was I read a thread where someone mentioned recursion was no longer the issue it was in 1.4, but since I have a stack version, it's not the end of the world.
FrostyCat: calling the script normally. It uses a ds_grid, not an array.
 

MishMash

Member
Best practise is to reduce your algorithm to an iterative form. Dynamic programming is a great technique, and can often lead to nicely presented solutions when you combine recursion with memoization. Fundamentally, recursion, whilst more well-defined, is often bad in practise due to the memory requirements. (Unless you have a good compiler which can perform tail recursion).

GM shouldn't really crash, it should error. However, for future reference, i'd avoid trying to use recursion anyway.
 

Posh Indie

Member
Also, if you're not already, you should use an array to pass the data in and access the array using the accessor. The reason being you can avoid a lot of overhead using the accessor instead of accessing the indices directly (which will remove the benefit of passing by reference).

From the documentation:
Arrays also have their own accessors which works in a similar way as those listed above for data structures. however array accessors have an interesting property and that is to permit you to modify an array from a script without having to copy it. When you pass an array into a script, it is passed by reference, meaning that the array itself isn't being copied into the script but rather it is simply being referenced to get the data. Normally if you then need to change the array, it would be copied to the script and then you would need to pass back the copied array for the original array to be updated. This can have costly processing overheads, and you can use the accessor instead, as that will change the original array directly without the need for it to be copied.
 
T

TimothyAllen

Guest
Also, if you're not already, you should use an array to pass the data in and access the array using the accessor. The reason being you can avoid a lot of overhead using the accessor instead of accessing the indices directly (which will remove the benefit of passing by reference).

From the documentation:
Arrays also have their own accessors which works in a similar way as those listed above for data structures. however array accessors have an interesting property and that is to permit you to modify an array from a script without having to copy it. When you pass an array into a script, it is passed by reference, meaning that the array itself isn't being copied into the script but rather it is simply being referenced to get the data. Normally if you then need to change the array, it would be copied to the script and then you would need to pass back the copied array for the original array to be updated. This can have costly processing overheads, and you can use the accessor instead, as that will change the original array directly without the need for it to be copied.
This is only true if writting to the array and doesnt apply to reading from the array. Actually I wouldnt be surprised if using the accessor while reading causes a perfomance hit.
 

GMWolf

aka fel666
Dynamic programming is a great technique
Dynamic programming is nice, but not a replacement for recursion. In many cases, dynamic programming requires you to compute more values than recursion.
Its also a heck of a lot more complicated to come up with dynamic programming aproaches to problems!
Some problems are still best tackled trhoug recursion. Though it must be said any recursive code can be written itterativly.
 

Posh Indie

Member
This is only true if writting to the array and doesnt apply to reading from the array. Actually I wouldnt be surprised if using the accessor while reading causes a perfomance hit.
This is true, I should have clarified (I kept using ambiguous terminology, sorry!). Arrays are passed by reference so I would hope reading from them without the accessor would respect that. When writing to the array (As stated) you should use the accessor.
 
Top