5 6 7 8 9 10 11

Tail recursion

14

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
Share this page:

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