Example using Z combinator to calculate Fibonacci in Lua

Fibonaccis.lua

fibonacciTailRec = function(n, val, prev)
  if n == 0 then
    return prev
  else
    return fibonacciTailRec(n - 1, val + prev, val)
  end
end

fibonacciCps = function(n, cont)
  if n < 2 then
    return cont(n)
  else
    return fibonacciCps(
      n - 1,
      function(v1)
        return fibonacciCps(
          n - 2,
          function(v2)
            return cont(v1 + v2)
          end
        )
      end
    )
  end
end

fibonacciDirect = function(n)
  if n == 0 then
    return 0
  elseif n == 1 then
    return 1
  else
    return fibonacciDirect(n - 1) + fibonacciDirect(n - 2)
  end
end

-- O = \g. g g
Omega = function(g)
  return g(g)
end

-- Z = \f. O (\g. f (\x. g g x))
Z = function(f)
  return Omega(
    function(g)
      return f(
        function(x)
          return g(g)(x)
        end
      )
    end
  )
end

protoFib = function(recur)
  return function(n)
    if n < 2 then
      return n
    else
      return recur(n - 1) + recur(n - 2)
    end
  end
end

fibonacciZ = Z(protoFib)

start_time = os.time()
print("Tail-recursive fibonacci: ", fibonacciTailRec(40, 1, 0))
print("Elapsed: ", os.difftime(os.time(), start_time))

start_time = os.time()
print("Directly recursive fibonacci: ", fibonacciDirect(40))
print("Elapsed: ", os.difftime(os.time(), start_time))

start_time = os.time()
print(
  "CPS-based fibonacci: ",
  fibonacciCps(
    40,
    function(x)
      return x
    end
  )
)
print("Elapsed: ", os.difftime(os.time(), start_time))

start_time = os.time()
print("Fixpoint-based fibonacci: ", fibonacciZ(40),
      "Elapsed: ", os.difftime(os.time(), start_time))

--[[ 

$ lua fix.lua
Tail-recursive fibonacci:       102334155   Elapsed: 0.0
Directly recursive fibonacci:   102334155   Elapsed: 7.0
CPS-based fibonacci:            102334155   Elapsed: 27.0
Fixpoint-based fibonacci:       102334155   Elapsed: 42.0

$ luajit fix.lua
Tail-recursive fibonacci:       102334155   Elapsed: 0
Directly recursive fibonacci:   102334155   Elapsed: 1
CPS-based fibonacci:            102334155   Elapsed: 24
Fixpoint-based fibonacci:       102334155   Elapsed: 32

]]