Lua declaring local variable in a recursive function

Question

I just started programming and choosed lua to write a script that processes a XML configuration file.

I load the XML file with LuaXML (C binding version) which maps it to a heavily nested table.

My problem came up when I tried to write a function that finds all matches to a tag in the xmltable. The matches are inserted in a table that is returned by the function. My problem is with the declaration of this table variable, that has to be local to function.

First I tried:

local result = result or {}

But this declares the variable with every recursion.

Finally I came up with this solution that works, but seems too complicated to me:

function findall_wrapper(xmltable, tag)

  local results = {}

  function findall(xmltable, tag)

    if xml.TAG == tag then table.insert (results, xmltable) end

    for k, v in pairs(xmltable) do
      if (type(v) == "table") then findall(v, tag) end 
    end
  end

  findall(xmltable, tag)
  return results

end

How can I solve this in a nicer, more elegant way? Why does local result = result or {} declares the variable with every recursion?

Sorry if the answer to my question is too obvious but as I mentioned, I just started programming.

Answer 1

If you mean that you didn't want to use a wrapper function then I think you came remarkably close. Was this is the sort of thing you were aiming for?

function findall(xmltable, tag, results)
    local results = results or {}
    if xmltable[xml.TAG] == tag then table.insert(results, xmltable) end
    for k, v in pairs(xmltable) do
      if type(v) == "table" then findall(v, tag, results) end
    end
    return results
end

Answer 2

Actually I think you have come up with a nice and elegant solution. What you are doing is exploiting that functions in Lua are closures, this can be a very useful technique when writing recursive function, which needs to build data structures while running. All you need to do to make it perfect, is to add the local keyword in front of function findall inside function findall_wrapper, then your helper function will be local, and wont pollute the global namespace.

To elaborate a bit:

There are two different type of functions, simple recursive functions and complex recursive functions. All recursive functions can be implemented in the following way:

function sum_list(l)
  if #l == 0 then
    return 0
  else
    local e = table.remove(l)
    return e + sum_list(l)
  end
end

print(sum_list({1,2,3,4}))
> 10

Here the call stack is used to store intermediate results, this can give you a very large stack with deep recursion or multiple calls to the function in the return.

A better way of doing it is called tail-recursion:

function sum_list(l, a)
  if #l == 0 then
    return a
  else
    local e = table.remove(l)
    return sum_list(l, a + e)
  end
end

print(sum_list({1,2,3,4}), 0)
> 10

In this example an accumulator is passed in the call, so the call stack is no longer used for storage, and if the implementation supports it, it can turn it into an iteration. Sadly not all recursive functions are tail-recursive. The problem with the accumulator in this case is that people have to instantiate it to zero, otherwise it gives a wrong result.

The solution to this, is just what you did:

function sum_list(l)
  local function sum_list_helper(l, a)
    if #l == 0 then
      return a
    else
      local e = table.remove(l)
      return sum_list_helper(l, a + e)
    end
  end

  return sum_list_helper(l, 0)
end

where a local function is created, which is then called with the correct instantiation value.