# Tail recursion

195

In Lua you can write loops in a functional way with tail recursion. However there is a certain restriction, so you should do tail call properly.

To do tail call properly you should write return statement as a single value statement. Let's see some examples:

``````function sum(n)
if n > 0 then
return n + sum(n - 1)
else
return 0
end
end

print(sum(10))``````
``55``

Alright, that works. However there is a problem. Look at the tail call:

``return n + sum(n - 1)``

This statement operates on two values. The first argument `n` should be kept until `sum(n - 1)` return a value. Which means stack frame cannot be discarded before the tail call: there is still something we need in future. Let's try it with a bigger value:

``````function sum(n)
if n > 0 then
return n + sum(n - 1)
else
return 0
end
end

print(sum(1000000))``````
``input:3: C stack overflow``

As you see, Lua compiler couldn't optimize our tail call which caused stack overflow. To fix that we should rewrite it in a single-value return statement:

``````function sum(n, accum)
if n > 0 then
return sum(n - 1, accum + n)
else
return accum
end
end

print(sum(1000000, 0)) -- Don't forget about the initial accum value``````

Instead of keeping addition arguments on the stack, we use an accumulator as a function parameter. Now we don't need to keep anything on every level of stack, so stack frames can be discarded. And now it works properly:

``500000500000``
Rate this post:

Lesson 7

Lesson 9

### Learning plan

A list of built-in operators in Lua
A list of Lua statements which you use to organize control flow of a program
What kind of functions are there and how to write them
8. Tail recursion
How to write tail recursion in Lua properly
9. Strings
How to define and work with strings
10. Arrays
How to deal with arrays or lists
11. Tables
Table is a general Lua data structure, it's all about tables