How can I prevent stack overflow from a recursive function?
Hi, I have one big table named tbl, and keys titled as Blocks. Here's an example of how I have each Block set up:
tbl.Block4 = {
{
{
Sensor = sensors.X3,
Signal = {
Model = signals.S3A,
PathOptions = {
{
Name = "Station",
Switches = {
[switches.V2] = 2
}
},
{
Name = "Main Line",
Switches = {
[switches.V2] = 1
}
}
}
}
}
},
{
{
Sensor = sensors.X4B,
Signal = {
Model = signals.S4B
}
},
{
Sensor = sensors.X4A,
Signal = {
Model = signals.S4A
}
}
}
}
I know, the tables go super deep, but I have it that way for a reason. My goal is to give each table with the sensor and signal inside it another table called "Adjacent", which contains the other table that has the same sensor value. I have a recursive function that I got with the help of the community here:
module.tableRec = function(tbl, func, level) --Add an OPTIONAL paremeter to be used in the recursion loop.
--If we weren't passed a recursion level, assume we are starting a recursion loop and set to 0
if not level then level = 0 end
--Add printouts for debugging. Also, use typeof - (it's more compatible with ROBLOX)
if typeof(tbl) ~= "table" then warn("Passed table not a table!") return end
for i, v in pairs(tbl) do
func(i, v, level)
if typeof(v) == "table" then --If we have found a table, call the recursive function on it!
module.tableRec(v, func, level + 1) --Add one to the current level to indicate a new level of recursion
end
end
end
Finally, this is what I'm doing to get the adjacent points. It seems to work, until a stack overflow happens.
function findAdjacent(value)
functions.tableRec(tbl, function(i, v, level)
local block
local endPoint
if level == 0 then
block = v
elseif level == 1 then
endPoint = v
elseif level == 2 then
if v ~= value and v.Sensor == value.Sensor then
print("found adjacent")
value.Adjacent = {block, endPoint, v}
end
end
end)
end
functions.tableRec(tbl, function(index, value, level)
if level == 2 then
findAdjacent(value)
end
end)
I would really appreciate how I could identify which tables share the sensors without putting too much stress on the game. Thanks!
1 answer
I'm not 100% sure why the stack overflow is happening, but you certainly have an inefficiency here. On line 18 you call the recursive function tableRec and pass in as an argument a function that calls findAdjacent which also calls tableRec.
Also note that your variables block and endpoint aren't going to be used in your findAdjacent function -- there is a different set of those local variables for every call to findAdjacent.
Recursion is best used when each child is identical to the parent, and each of their children are also identical (in what keys they have, not their values). In your case, for instance, not everything has a "Sensor"; many of the levels appear to just be lists.
A better strategy is to use for loops to navigate the entire table once and keep track of which sensors are used by which tables:
local sensorToList = {}
for _, block in pairs(tbl) do
for _, endPoint in pairs(block) do
for _, obj in pairs(endPoint) do
local list = sensorToList[obj.Sensor]
if not list then
list = {}
sensorToList[obj.Sensor] = list
end
list[#list + 1] = {Block = block, EndPoint = endPoint, Value = obj} -- or {block, endPoint, obj}
end
end
end
for sensor, list in pairs(sensorToList) do
-- Do something with sensor and/or list here
-- ex, if everything is always adjacent to one other thing, then #list == 2, so:
list[1].Value.Adjacent = list[2]
list[2].Value.Adjacent = list[1]
-- but say the number of adjacent isn't guaranteed, you might want a list of adjacents:
for i = 1, #list do -- For each value
-- Add every other value into a new adjacency list
local adjacentList = {}
for j = 1, #list do
if i ~= j then
adjacentList[#adjacentList + 1] = list[j]
end
end
list[i].Adjacent = adjacentList
end
end
0