# Having problems writing a recursive function in Lua - looking for help & suggestions!

I'm on a Mac, using Nova for development, but I don't think it's relevant to this issue.

Basically, I’m trying to create a recursive function in Lua… and one of my tables doesn’t seem to be working correctly the second time through the recursion loop. First time everything works right, but the second time the variable’s count is always 0 (using the `#variable` method of getting the count).

Apologies in advance for this relatively long code block. I'm not sure if there's a better way to post this.

So the relevant bits are the very last function (which I’m calling from main.lua), and the loop in `indexesOfFirstMatchingGroup` …which calls `matchingAdjacentIndexes` (the recursive bit).

``````import 'CoreLibs/object'

class('Game').extends()

--Game = {}
--Game.__index = Game

-- Note that values > 99 are reserved for non-game states
-- and will generally be ignored by most of these functions.

local grid = {}
local w
local h

local valueDefault = 1
local valueEmpty = -1
local valueMaxForRandom = 6

Directions = {UP = "1", DOWN = "2", LEFT = "3", RIGHT = "4"}

function Game:init(width, height)
Game.super.init(self)
w = width
h = height
self:resetGrid()
end

function Game:indexForXY(x, y)
if x < 1 or y < 1 or x > w or y > h then return 1 end
return ((y-1) * w) + x
end

function Game:valueForXY(x, y)
if x < 1 or y < 1 or x > w or y > h then return valueEmpty end
return grid[self:indexForXY(x, y)]
end

function Game:inBounds(x, y)
if x < 1 or y < 1 or x > w or y > h then
return false
else
return true
end
end

function Game:setValueForXY(newValue, x, y)
if x < 1 or y < 1 or x > w or y > h then return end
grid[self:indexForXY(x, y)] = newValue
end

function Game:printGrid()
local rows = "grid (w:" .. w .. ",h:" .. h .. ") \n"
for y = 1, h do
local row = " [ "
for x = 1, w do
row = row .. grid[self:indexForXY(x, y)] .. ", "
end
row = row .. "]\n"
rows = rows .. row
end
print(rows)
end

function Game:randomizeGrid()
for x = 1, w do
for y = 1, h do
grid[self:indexForXY(x, y)] = math.random(1,valueMaxForRandom)
end
end
end

function Game:resetGrid()
for x = 1, w do
for y = 1, h do
grid[self:indexForXY(x, y)] = valueDefault
end
end
end

function Game:setGrid(gridTable)
-- this seems like the safest way to do this
local index
for x = 1, w do
for y = 1, h do
index = self:indexForXY(x, y)
grid[index] = gridTable[index] or valueDefault
end
end
end

function Game:swapGridValues(x1, y1, x2, y2)
local value1 = self:valueForXY(x1, y1)
grid[self:indexForXY(x1, y1)] = self:valueForXY(x2, y2)
grid[self:indexForXY(x2, y2)] = value1
end

function Game:valueInDirection(direction, fromX, fromY)
if direction == Directions.UP then
return self:valueForXY(fromX, fromY-1)
elseif direction == Directions.DOWN then
return self:valueForXY(fromX, fromY+1)
elseif direction == Directions.LEFT then
return self:valueForXY(fromX-1, fromY)
elseif direction == Directions.RIGHT then
return self:valueForXY(fromX+1, fromY)
else
return valueEmpty
end
end

-- functions past this point are really pretty specific to this game

function Game:indexesOfFirstMatchingGroup()
local currentValue
for x = 1, w do
for y = 1, h do
currentValue = self:valueForXY(x, y)
-- don't try to match values of defaultValue or > 99
if currentValue > 1 and currentValue < 100 then
local checkedIndexes = {}
local matchingIndexes = {}
checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(currentValue, x, y, checkedIndexes, matchingIndexes)
if #matchingIndexes > 1 then
return matchingIndexes
end
end
end
end
-- no matches found
return {}
end

function Game:matchingAdjacentIndexes(value, x, y, checkedIndexes, matchingIndexes)
print("in matchingAdjacentIndexes for x,y: " .. x .. "," .. y)
if not self:inBounds(x, y) then
print("  returning OOB")
return checkedIndexes, matchingIndexes
end
local currentIndex = self:indexForXY(x, y)
if checkedIndexes[currentIndex] == true then
return checkedIndexes, matchingIndexes
end
checkedIndexes[currentIndex] = true
if grid[currentIndex] ~= value then
print("  returning values (" .. value .. "," .. grid[currentIndex] .. ") do not match")
return checkedIndexes, matchingIndexes
end
matchingIndexes[currentIndex] = true
print("  found match, matchingIndex count: " .. #matchingIndexes)
checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x, y-1, checkedIndexes, matchingIndexes)
checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x, y+1, checkedIndexes, matchingIndexes)
checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x-1, y, checkedIndexes, matchingIndexes)
checkedIndexes, matchingIndexes = self:matchingAdjacentIndexes(value, x+1, y, checkedIndexes, matchingIndexes)
print("  checked all directions (" .. x .. "," .. y .. "), matchingIndex count: " .. #matchingIndexes)
return checkedIndexes, matchingIndexes
end

function Game:removeMatchingTiles()
-- note, only values between 2 and 99 will be checked and
-- if they have any neighbors that match, they will be
-- replaced with 1, (the default value)
-- this function returns the number of tiles removed
local matchesFound = 0
local currentIndex
local currentValue
local indexHasMatch = {}
for x = 1, w do
for y = 1, h do
currentIndex = self:indexForXY(x, y)
currentValue = grid[currentIndex]
if (currentValue > 1 and currentValue < 99) and (
(currentValue == grid[self:indexForXY(x+1, y)]) or
(currentValue == grid[self:indexForXY(x-1, y)]) or
(currentValue == grid[self:indexForXY(x, y+1)]) or
(currentValue == grid[self:indexForXY(x, y-1)])) then
indexHasMatch[currentIndex] = true
matchesFound += 1
end
end
end
if matchesFound > 0 then
for x = 1, w do
for y = 1, h do
currentIndex = self:indexForXY(x, y)
if indexHasMatch[currentIndex] then
grid[currentIndex] = 1
end
end
end
end
return matchesFound
end

local defaults = self:defaultIndexes()
if #defaults == 0 then return end
local key = defaults[math.random(1,#defaults)]
grid[key] = math.random(2,valueMaxForRandom)
end

-- returns a table of grid indexes with default values
function Game:defaultIndexes()
local defaultKeys = {}
for key, value in ipairs(grid) do
if value == valueDefault then
table.insert(defaultKeys, key)
end
end
return defaultKeys
end

function Game:allValuesAreDefault()
local currentValue
for x = 1, w do
for y = 1, h do
currentValue = self:valueForXY(x, y)
if currentValue < 99 and currentValue ~= valueDefault then
return false
end
end
end
return true
end

local foundOne = false
local checkedIndexes = { }
local currentIndex = 1
local checkIndex = 1
for x = 1, w do
for y = 1, h do
currentIndex = self:indexForXY(x, y)
-- need to exclude cursor values
if grid[currentIndex] > 99 then
checkedIndexes[currentIndex] = true
end
-- only need to check this index if we haven't checked it already
if checkedIndexes[currentIndex] ~= true then
foundOne = false
-- down
checkIndex = self:indexForXY(x, y+1)
if grid[currentIndex] == grid[checkIndex] then
foundOne = true
checkedIndexes[currentIndex] = true
checkedIndexes[checkIndex] = true
end
-- right
if foundOne == false then
checkIndex = self:indexForXY(x+1, y)
if grid[currentIndex] == grid[checkIndex] then
foundOne = true
checkedIndexes[currentIndex] = true
checkedIndexes[checkIndex] = true
end
end
-- up
if foundOne == false then
checkIndex = self:indexForXY(x, y-1)
if grid[currentIndex] == grid[checkIndex] then
foundOne = true
checkedIndexes[currentIndex] = true
checkedIndexes[checkIndex] = true
end
end
-- left
if foundOne == false then
checkIndex = self:indexForXY(x-1, y)
if grid[currentIndex] == grid[checkIndex] then
foundOne = true
checkedIndexes[currentIndex] = true
checkedIndexes[checkIndex] = true
end
end
if foundOne == false then
return false
end
end
end
end
return true
end

function Game:testIndexesOfMatchingGroups()
local game = Game(5, 6)
local tempGrid = {
2, 1, 2, 1, 5,
1, 1, 1, 1, 1,
1, 1, 100, 1, 1,
1, 1, 1, 4, 1,
1, 1, 4, 4, 1,
3, 3, 1, 1, 4,
}
game:setGrid(tempGrid)
local matchingIndexes = game:indexesOfFirstMatchingGroup()
print("number of matching indexes is: " .. #matchingIndexes)
--	assert(#matchingIndexes == 3, "no matching indexes found")
end
``````

So all the print statements in `matchingAdjacentIndexes` are to try and fix this problem. (I can see it “working” first time by replacing a 1 next to the initial 2 in my grid with another 2, which correctly returns a `matchingIndexes` table with 2 or 3 elements in it.)

As is, it outputs the following:

``````in matchingAdjacentIndexes for x,y: 1,1
found match, matchingIndex count: 1
returning OOB
returning values (2,1) do not match
returning OOB
returning values (2,1) do not match
checked all directions (1,1), matchingIndex count: 1
found match, matchingIndex count: 0
returning values (3,1) do not match
returning OOB
returning OOB
found match, matchingIndex count: 0
returning values (3,1) do not match
returning OOB
returning values (3,1) do not match
checked all directions (2,6), matchingIndex count: 0
checked all directions (1,6), matchingIndex count: 0
<snipped the rest>
``````

Plus a bunch more that I deleted. Anyway, I’d expect the lines that say “found match, …” and the ones that say “checked all directions…” to end with values of 1 or higher. But you can see after the first time through they’re always zero.

A little more on what this code is trying to do: This is a relatively "generic" model for a grid-based game. The `indexesOfFirstMatchingGroup` function should return a table whose indexes correspond to the indexes of the grid that contain adjacent "groups" of matching values. (Doesn't matter what the values are, as long as they're >1 and <99.)

Incidentally, when I'm confident this code is working pretty well, I'll probably release it in some form somewhere. I'm happy to let anyone use it. (This is the umpteenth time I've written almost this exact class in various languages/environments.)

The problem is actually not the recursive code, it's in my lack of understanding how the `#table` count works. (And how it wouldn't work in my case.)

I found the solution essentially by reading the comments here: How to get number of entries in a Lua table? - Stack Overflow

1 Like