O'Reilly logo

Functional Programming: A PragPub Anthology by Michael Swaine

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Recursion in Lua

Recursive functions eventually call themselves, like this:

 function factorial (n)
  if n == 0 then
  return 1
  else
  return n * factorial(n - 1)
  end
 end
 print(factorial(5)) --> 120

Easy to follow, but executing this function for some values of n will result in a stack overflow error. That’s because on each successive invocation of factorial(n - 1), the machine must retain a reference to the previous iteration on its stack. The stack is finite, so it eventually runs out of space and the program explodes:

 print(factorial(-1))
 lua: factorial.lua:5: stack overflow
 stack traceback:
  factorial.lua:5: in function 'factorial'
  factorial.lua:5: in function 'factorial'
  ...

Lua 5.0 added proper tail calls, a sort of functional ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required