Optimization of Loops and conditionals in Recursive Lua Function-CodePudding

The following is the code of my function 


function myfunction ( ... )
  local tbl = table.pack(...)
  for _, v in ipairs(tbl) do
  if type(v) ~= 'number' then
  print('Error: Something different is expected.') 
  return
  elseif v~= math.abs(v) then
   print('Error: Your input needs slight modification.')
   return
  end
  end
 
    if some condition then 
      **recursive call to myfunction**
    else
      some result
    end
  end

The function works fine and it gives expected results to me. But the problem as one can observe that function is calling itself in recursive manner. So the first part of the code which I am giving below also gets repeated several times during each recursive call. Obviously I want to check input only once and exit the function if it is incorrect. If input is correct, then it should not be checked every recursive call. So how the code can be optimized for this purpose. Can some value be assigned to global variable and then use it somewhere inside the function (in if else condition) to avoid repetition. But again the check for value will get repeat (though it is less costly compared to the current approach. The problem is to avoid repetition of the following code (which is part of above code).

for _, v in ipairs(tbl) do
  if type(v) ~= 'number' then
  print('Error: Something different is expected.') 
  return
  elseif v~= math.abs(v) then
   print('Error: Your input needs slightly modified')
   return
  end
  end

As an example, consider the following function.

function factorial(n)
    if (n == 0) then
        return 1
    else
        return n * factorial(n - 1)
    end
end

When factorial(9.3) is executed it results into stack overflow as no error input check is involved. To handle this the following error mechanism is added.

function factorialwithinputcheck(n)
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * factorialwithinputcheck(n-1)
    end
end

This function gives error and stops execution whenever input is incorrect. The factorialwithinputcheck(9.3) doesn't result into stack overflow. But again the input check is made in every recursive call. How this code for example can be optimised?

CodePudding user response：

Being more specific as in my comment, I'd propose something like this:

function _factorial(n)
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

function factorialwithinputcheck(n)
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

or hiding _factorial:

function factorialwithinputcheck(n)
    local function _factorial(n)
        if (n == 0) then
            return 1
        else
            return n * _factorial(n-1)
        end
    end
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

but again, I'm not completely sure if this way the _factorial function has to be "created" multiple times (which should have a performance impact as well). But maybe this can be figured out with some benchmarking.

~~EDIT: Oh and if you want some input sanitizing: Up to now, you don't check for negative numbers.~~

Edit2: And since you ask for general optimization of your factorial function. Yes of course one could convert the recursive procedure into an iterative one (avoiding creating new stack frames that many times).

Using some sort of accumulator (acc) passing n*acc down to the next call, you could alternatively make the function tail recursive, (according to this pil chapter (I hope there is no change in that in more frequent lua verions) lua will then handle this for you). For example:

local function factorial_rec(n)
    local function _factorial(n)
        if (n == 0) then
            return 1
        else
            return n * _factorial(n-1)
        end
    end
  if type(n) ~= 'number' then
    error('only numbers are expected')
    return
elseif n~= math.floor(n)  or n~=math.abs(n) then
  error('only positive integers are expected')
  return
end
    if (n == 0) then
        return 1
    else
        return n * _factorial(n-1)
    end
end

(but to be honest I don't see much of a performance boost with this (0.000293s vs 0.000354s if I loop over factorial form 0 to 40, numbers starting with 21! are already beyond the range for numbers in lua (for my installation), checked only with a very rudimentary benchmark))