# Will this recursive function cause stack overflow?

I have the following function in one of my cleanup modules

``````local function CleanUp(Table,ObjectToIgnore)
for index, datatype in pairs(Table)do
Table[index] = nil
if DataTable[typeof(datatype)] then
DataTable[typeof(datatype)](datatype,ObjectToIgnore)
elseif typeof(datatype) == "table" then
CleanUp(datatype,ObjectToIgnore)
end
end
return nil
end
``````

Since this function calls itself and other functions based on their datatypes, I wonder if this would cause stack overflow. If it does, how would I make it so that it doesnâ€™t cause stack overflow

If the function keeps on calling itself, and has no way out, it will cause a stack overflow. I donâ€™t know the circumstances of your function, so for all I know it could or could not cause one. Itâ€™s up to you to prevent the overflow.

Well its a table that has references to events and roblox instances and sometimes nested tables, so I believe it wouldnâ€™t keep calling itself forever. Also, I canâ€™t really make a cat call here or my loop will break.

This one shouldnâ€™t, as long as you donâ€™t have weird stuff like the table containing references to itself.

The general rule for recursion is that with each recursive call the input should get smaller or the result should approach the exit condition. So when recursing through a table the exit condition is when you reach a sub-table that doesnâ€™t contain any other sub-tables.

1 Like

so if my subtables donâ€™t have any subtables within them I should be fine?

It should be fine as long as the table doesnâ€™t contain any circular references to itself.

Such as this:
This would cause a stack overflow:

``````local function traverse(t)
for i, v in pairs(t) do
print(i, v)
if (typeof(v) == "table") then
traverse(v)
end
end
end

local sample = {
a = 1,
b = 2,
c = 3
}
sample["d"] = sample -- circular reference

traverse(sample) -- will cause a few seconds lag then script timeout error
``````

However this could be avoided with some dynamic programming:

``````local function secureTraverse(t, mem)
if (mem == nil) then mem = {} end
mem[t] = true
for i, v in pairs(t) do
print(i, v)
if (typeof(v) == "table" and mem[v] == nil) then
secureTraverse(v, mem)
end
end
end

local sample = {
a = 1,
b = 2,
c = 3
}
sample["d"] = sample -- circular reference

secureTraverse(sample) -- should print:
--[[
a 1
b 2
c 3
d table: 0x...
]]
``````

But still, if there is no possibility of circular references, there is nothing to worry about.

yeah I see, I never reference the table itself as a value so it wouldnâ€™t be a problem. Thanks!

1 Like

If the function is calling it self too fast, it wonâ€™t cause a stack overflow but a script timeout. Stack overflow is caused when you try to allocate stacks more than the maximum which is 16381, hence â€śoverflowâ€ť.

I think OP originally meant to say timeout. In a lot of other languages infinite recursion will cause a stack overflow for the reason you mentioned, so thatâ€™s probably where he got the term from. But yes I agree Iâ€™ve never seen lua in Roblox throw a stack overflow error; itâ€™s always â€śScript timeout: exhausted allowed execution timeâ€ť.

1 Like