Interlude 7 - Recursion & Closures in Lua (Updated 23/01/16)

Webcomic Courtesy of Ethanol & Entropy

Interlude 7.1 Preamble

Before part 2 of the MineSweeper tutorial, we need to go over two concepts which you may not have come across before, namely recursion and closures. Writing recursive code is a fairly common technique but Lua is the first language that we have come across that uses closures.

Interlude 7.2 Recursion

Recursion in programming is using a function to call itself to solve a problem. The example given in every lecture on computer science is calculating the factorial of a number. We can't think of a better example so let's go with that.

What is a factorial? Well we are glad you asked. The factorial of an integer n greater than 0 (designated by n!) is the product of all positive integers less than or equal to n. So factorial five is:

5! = 5 x 4 x 3 x 2 x 1 = 120

Note that factorial zero is defined as 1. The iterative solution to a factorial function, could look something like this:

-- Given a number 'n' calculate its factorial the iterative way

function factorial(n)

    if n == 0
        return 1

    local temp = 1

    for i = 1, n do
        temp = temp * i
    end

    return temp

end

And the recursive version:

-- Given a number 'n' calculate its factorial the recursive way

function factorial(n)

  if n == 0 then
      return 1
  else
      return n * factorial(n - 1)
  end

end

The recursive version will be marginally slower, it is a bit shorter to code, and it is a bit simpler and closer to the mathematical definition of recursion. For very large values of n, the recursive function will crash due to a stack overflow. Every time a recursive call is made, the function clones itself and pushes the previous function onto the stack. You can only do this so many times before running out of memory.

There are two rules for using recursion:

1. If you use recursion then you must always have a base case which stops your code from calling itself forever. This won't happen of course, instead your program will crash with a stack overflow when it runs out of memory. The base case for the factorial function is n == 0.
2. Your function must also make progress towards your base case or you will be caught in infinite recursion and crash. In the factorial example, each recursive call decrements n, so eventually it will get to the base case of zero.

The advantage of a recursive solution is its simplicity and elegance, the disadvantage can be the speed and the amount of memory used if the depth of recursion is large.

The MineSweeper game uses recursion to reveal the neighbouring cells if you tap a cell with no neighbouring mines. Have a look at the revealCell() function in the Main class.

Interlude 7.3 Tail Recursion

@gunnar_z had the following to add on the topic of recursion: 

"Lua supports something called tail recursion, or tail calls. The idea is that if the calling function does not actually do anything else but return to its caller after the called function has returned, the call is basically replaced by a jump and the current stack frame is reused. That is, the call needs to have the form "return fun(args)". With a bit of thinking, this can be made to work with a lot of recursive problems. For your example (factorial), it might look like this:

function fact(n, s)

    s = s or 1
    if n == 0 then
        return s
    else
        return fact(n-1, s*n)
    end

end

Recursion is a bit slower than iteration for trivial problems, but that is hardly noticable. For non-trivial problems (for example a recursive vs. iterative implementation of a quicksort or a tree traversal algorithm), this difference in speed shrinks rapidly, as you (may) need a stack for them anyway, and it may even be faster to implicitly use the stack provided by the language runtime through recursion than to simulate your own."

Interlude 7.4 Closures

When a function is enclosed in another function, then it has access to all the local variables of that function. This is called lexical scoping and the external local variable is called an "upvalue". 

To understand how this is useful, consider if we wanted to create a calculator application. This has a number of digit buttons that we display on the screen.

function digitButton (digit) 
    return Button{ label = digit, action = function () add_to_display(digit) end } 
end

In this example, we assume that Button is a class that creates new buttons; label is the button label; and action is the callback function to be called when the button is pressed. (It is actually a closure, because it accesses the upvalue digit.)

In our MineSweeper game, the inNeighbourCells() function uses closures to access the cell index upvalues and count the number of mines in neighbouring cells.

Another use for closures is to produce an iterator.

function makeIterator()

    local n = 0

    function iterator()
        n = n + 1
        return n
    end

    return iterator

end

-- Make two different iterator's

iterator_a = makeIterator()
iterator_b = makeIterator() 

print(iterator_a())         -- Will print 1
print(iterator_a())         -- Will print 2
print(iterator_b())         -- Will print 1
print(iterator_a())         -- Will print 3
print(iterator_b())         -- Will print 2

Once again we have a function within a function. makeIterator() is a constructor of iterator()'s and every time iterator() gets called it can see the upValue n and increments it.

@gunnar_z contributed the following additional information on closures:

"Closures are created whenever a function is created in a lexical block, not only within functions. When a function is created in a do .. end block, or even within a loop, it creates a closure. Also, all functions created within a file (or a tab in the codea world) are closures existing in the lexical context of that file (or tab). Btw. some time ago the scoping of the 

for i=1,n do ... end

construct was changed to create a new scope for every iteration. Thus, the following:

t={}

for i=1,10 do
    t[i] = function() print(i) end

end

will create a table with 10 functions, each one printing the value of i during its iteration."