6 posts
Posted 30 June 2016 - 02:34 PM
I have problems with stack overflow. I want to learn how to use recursive functions avoiding a stack overflow, if is posible. If not, I need help implementing a tree. In my code got a stack overflow when i try to create one, if has a big size(height). There is my attempt to make a tree.
Node={}
function Node.new(n)
local self={}
local childrenL=nil
local childrenR=nil
local value=n
function self.addChildren(_n)
if _n<value then
if childrenL==nil then
childrenL=Node.new(_n)
else
childrenL.addChildren(_n)
end
else
if childrenR==nil then
childrenR=Node.new(_n)
else
childrenR.addChildren(_n)
end
end
end
function self.getValue()
return n
end
function self.dfs()
print(n)
os.sleep(0.05)
if childrenL~=nil then childrenL.dfs() end
os.sleep(0.05)
if childrenR~=nil then childrenR.dfs() end
end
return self
end
tree=Node.new(0)
for i=1, 500 do
tree.addChildren(i*-1)
print ("inserted child "..i*-1)
os.sleep(0)
end
tree.dfs()
Thanks in advance.
2427 posts
Location
UK
Posted 30 June 2016 - 04:28 PM
does it work if you use a smaller number of trees? so instead of 500 you try 10
6 posts
Posted 30 June 2016 - 04:44 PM
does it work if you use a smaller number of trees? so instead of 500 you try 10
Yes, it works with small height tree. But I can't assume a maximum size.
7083 posts
Location
Tasmania (AU)
Posted 30 June 2016 - 04:47 PM
You could get away with tail calling within your addChildren functions, but not within your dfs functions. If you want to stick that many children on the one branch you'll simply have to avoid function recursion.
Typically the best way to achieve that is to use tables within regular loops. This should give identical functionality with no recursion at all:
Spoiler
local Node = {}
function Node.new(rootValue)
local self, tree = {}, {value = rootValue}
function self.addChildren(newValue)
local curIndex = tree
while true do
local side = (newValue < curIndex.value) and "left" or "right"
if curIndex[side] then
curIndex = curIndex[side]
else
curIndex[side] = {value = newValue, parent = curIndex}
return
end
end
end
function self.getValue()
return rootValue
end
function self.dfs()
local curIndex, last = tree, tree
repeat
if last ~= curIndex.left and last ~= curIndex.right then
print(curIndex.value)
sleep(0.05)
end
local oldIndex = curIndex
if curIndex.left and last ~= curIndex.left and last ~= curIndex.right then
curIndex = curIndex.left
elseif curIndex.right and last ~= curIndex.right then
curIndex = curIndex.right
else
curIndex = curIndex.parent
end
last = oldIndex
until not curIndex
end
return self
end
local tree = Node.new(0)
for i = -1, -500, -1 do
tree.addChildren(i)
print("inserted child "..i)
os.sleep(0)
end
tree.dfs()
6 posts
Posted 30 June 2016 - 05:40 PM
Thanks Bomb Bloke. It works. And now I know that I can't use recursion except if it fits for tail-recursion. When you can't use recursion, the code gets more complicated.