Interlude 7 - Recursion and Closures in Lua

I have stuck up a tutorial on recursion and closures over at

I’m new to closures so let me know if I have hold of the wrong end of the stick. Any comments and suggestions are most appreciated.

nice :slight_smile: A few notes, if I may:

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 0
  if n == 0 then
    return s
    return fact(n-1, s*n)

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.

Concerning the 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:

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

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

@gunnar_z - excellent thanks for the comments, I will update over the weekend.

Particularly the bit on closures within a lexical block, I hadn’t picked up on that.

Thanks again for adding that extra bit of polish and depth. Have you been using Lua long?

@reefwing erm… yes. Since around 2003 :wink: