Lua - Proper tail calls

Proper tail calls, PTC is an optimization technique employed by many programming languages during a recursion call. In PTC, when a last call of the function is a call to another function, calling function's stack frame is reused. Lua implements Proper Tail Calls. Using PTC, Lua prevents stack from indefinitely growing to avoid stack overflow errors.

When a recursive call of a function ends by calling another function, Lua is not creating a new stack frame. Lua reuses the current stack frame by making a jump to the new function.

Example - Proper Tail Call

main.lua

function helper(n, accumulator)
  if n == 0 then
    -- Proper tail call
    return accumulator
  else
    -- proper tail call
    return helper(n - 1, n * accumulator) 
  end
end

function factorial(n)
  -- proper tail call
  return helper(n, 1) 
end

-- although very large number of iterations, but no stack overflow, 
-- we can use large number as well 
print(string.format("%.0f",factorial(10))) 

Output

When the above code is built and executed, it produces the following result −

3628800

In order to use proper tail calls in recursive implementations, the another function call must be the last call before it returns. Funtion call must be preceded with return statement and there should not be any other operation in same statement.

In above example factorial is the recursive function which is calling helper function as a last action. Due to PTC, proper tail optimization, Lua reuses the stack frames during recursive calls thus prevents the stack overflow even for very high values of n.

Examples - No Proper Tail Calls

Following are examples of improper tail calls as last function call is not the last action before the final return.

function f1(x)
   -- return is not specified before g(x), implicit return will be called after g(x)
   g(x)
end

function f2(x)
   -- addition of 1 is last operation instead of g(x)
   return g(x) + 1
end

function f3(x)
   -- logical OR operation is the last operation
   return x or g(x)
end

function f4(x)
   -- being enclosed in parenthesis, g(x) is not last operation as adjustment can happen
   return (g(x))
end

function f5(x)
   -- return is the last operation instead of g(x)  
   g(x); return 
end

function f6(x)
   -- result of g(x) is used by h(), thus not the last operation
   return h(g(x)) 
end

Advantages of Proper Tail Calls

• Prevents Stack Overflow − Proper Tail Calls optimization enables recursive implementations without risk of stack overflow by exceeding call limits.

• Highly Efficient − As new stack frames are not created for each call, overhead of creating stack frame is reduced thus improves the efficiency of recursive calls.

• Facilitates Functional Programming − Using PTC, recursive patterns can be applied effectively in functional programming scenarios.

• Implement State Machines − State machines can be implemented easily where we need to represent transitions between states as function calls.