Laurie White’s Blog

So, Lua optimizes tail recursion calls.

At first glance, this is no big deal. Very few recursive functions are tail recursive, that is, have the recursive call as the very last thing in the function, at first glance.

Consider the recursive factorial, for a real easy example.

function fact_1(num)
   if num <= 1 then
      return 1
   else
      return num * fact_1 (num - 1)
   end
end

While it looks like the recursive call is the last thing in the function, it really isn’t. The multiplication of num and the result of the result of the recursive call is the last thing done in the function, so this isn’t tail recursion.

But it can be “easily” turned into a function that is tail recursive. I quote “easily” since the first two or three or ten times you see the “easy” translation, you may not believe it, or at least may not believe it’s really easier. (I had students who figured it out the first time and others who took a lot more tries.  A lot more.)

What you have to do is carry the result with you down into the recursion. You’ll update the solution as you go, so that when you finally get to the base case, you’ll have the result ready to return. As the last step of the function. Thus, tail recursion. Code to do this is:

function fact_2 (num, result)
   if num <= 1 then
      return result
   else
      return fact_2 (num - 1, result * num)
   end
end

The only thing left to do is to rewrite the main factorial function to use this tail recursive version:

function factorial (num)
   return fact_2(num, 1)
end

Does it really matter? Does Lua really optimize tail recursion?

I tried the following non-tail recursive code and could compute up to 19,997 before getting a stack overflow error.

function sum_badly(max)
   if max <= 1 then
      return max
   end
   local other_sum = sum_badly(max - 1)
   return other_sum + max
end

And sure enough, the tail recursive version below allowed me to go to at least 100,000,000, so I’m convinced Lua does optimize tail recursion.

function sum_well_helper(max, current)
   if max < 1 then
      return current
   else
      return sum_well_helper(max -1, current + max)
   end
end

function sum_well(max)
   return sum_well_helper(max, 0)
end

The code is in my GitHub account if you want to see for yourself. The solutions to the Day 1 problems are also there.

That’s enough of Day 1 for now. Onto to tables.