logoalt Hacker News

noriryesterday at 7:02 PM0 repliesview on HN

It is simple to convert factorial to tail recursive form. In lua, which has tco:

    local factorial do
      local function impl(n, acc)
        if n == 1 then
          return acc
        else
          return impl(n - 1, acc * n)
        end
      end
      factorial = function(n)
        if n < 0 then
          error("factorial input is negative")
        elseif n <= 1 then
          return 1
        else
          return impl(n - 1, n)
        end
      end
    end
You could replace impl with an imperative loop:

    local acc = 1
    repeat
      acc = acc * n
      n = n - 1
    until n == 1
    return acc
Personally, I find this ugly compared to the tail recursive solution. The loop version only seems more natural if you primarily think in loops. Tail recursion is strictly more powerful than looping since every imperative loop can trivially be converted to a tail recursive function, but the reverse is not true.