Will this recursive function cause stack overflow?

Help and Feedback Scripting Support
#1

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

#2

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.

#3

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.

#4

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
#5

so if my subtables don’t have any subtables within them I should be fine?

#6

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.

#7

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

1 Like
#8

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”.

#9

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