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.

### Like this:

Like Loading...

*Related*

## Leave a Reply