如何尾递归实现组合？

我想我找到了一种方法来实现这个：

function combinations (array, m)

  local dropfirst = function (array)
    return {table.unpack(array, 2, #array)}
  end

  local append = function (array, item)
    local copy = {table.unpack(array)}
    copy[#copy + 1] = item
    return copy
  end

  local _combinations
  _combinations = function (sequence, m, prefix, queue)
    local n = #sequence
    local newqueue
    if n >= m then
      if m == 0 then
        print(table.unpack(prefix))
      else
        local deleted = dropfirst(sequence)
        if n > m then
          newqueue = append(queue, {deleted, m, prefix})
        else
          newqueue = queue
        end
        return _combinations(deleted, m - 1,
                             append(prefix, sequence[1]),
                             newqueue)
      end
    end
    if #queue > 0 then
       newqueue = dropfirst(queue)
       local newargs = append(queue[1], newqueue)
       return _combinations(table.unpack(newargs))
    end

  end

  _combinations(sequence, m, {}, {})

end

我认为这个版本是尾递归的。不幸的是，它不能像我的原始非尾递归版本一样以好的顺序打印结果（更不用说代码的复杂性了），但是有时候至少可以得到部分结果。

编辑：好吧，是的，有时候一切都能够实现！下面的版本是尾递归的，同时以与原始非尾递归版本相同的顺序打印它的结果：

function combinations (sequence, m, prefix, stack)
  prefix, stack = prefix or {}, stack or {}

  local n = #sequence
  if n < m then return end

  local newargs, newstack
  if m == 0 then
    print(table.unpack(prefix))
    if #stack == 0 then return end
    newstack = droplast(stack)
    newargs = append(stack[#stack], newstack)
  else
    local deleted = dropfirst(sequence)
    if n > m then
       newstack = append(stack, {deleted, m, prefix})
    else
       newstack = stack
    end
    local newprefix = append(prefix, sequence[1])
    newargs = {deleted, m - 1, newprefix, newstack}
  end

  return combinations(table.unpack(newargs)) -- 尾递归

end

它使用以下辅助函数：

function append (sequence, item)
  local copy = {table.unpack(sequence)}
  copy[#copy + 1] = item
  return copy
end

function dropfirst (sequence)
  return {table.unpack(sequence, 2, #sequence)}
end

function droplast (sequence)
  return {table.unpack(sequence, 1, #sequence - 1)}
end

示例：

> combinations({1, 2, 3, 4, 5}, 3)
1   2   3
1   2   4
1   2   5
1   3   4
1   3   5
1   4   5
2   3   4
2   3   5
2   4   5
3   4   5

具有讽刺意味的是，这个版本通过实现自己的堆栈来实现尾递归，所以我不确定它是否最终比非尾递归版本好...不过，我猜测函数的stack实际上是存在于堆（是吗？）中的，因为 Lua 的表是通过引用传递的（对吗？），所以也许这是一个进步（如果我错了，请纠正我！）。

有第三个选择，这个选择不会导致蛇咬自己的尾巴。虽然使用尾递归不会导致堆栈溢出，但是出于个人喜好，我避免使用尾递归。我使用 while 循环和一个保存每次迭代信息的堆栈。循环中，您从堆栈中弹出下一个任务，执行工作，然后将下一个任务压入堆栈。我认为这看起来更干净，更容易理解嵌套结构。

这是我将您的代码翻译成我的写法的方式：

function combinations(sequence, item)
    local function append(array, item)
        local copy = {table.unpack(array)}
        copy[#copy + 1] = item
        return copy
    end

    local stack = {}
    local node = { sequence, item, {} }

    while true do
        local seq = node[1]
        local itm = node[2]
        local pre = node[3]

        local n = #seq
        if itm == 0 then
            print(table.unpack(pre))
        elseif n < itm then
            -- do nothing
        else
            local reserve = {table.unpack(seq, 2, #seq)}
            table.insert(stack, { reserve, itm, pre })
            table.insert(stack, { reserve, itm-1, append(pre, seq[1]) })
        end

        if #stack > 0 then
            node = stack[#stack] -- LIFO
            stack[#stack] = nil
        else
            break
        end
    end
end

您可以将这种 while 循环堆栈/节点技术用于几乎任何递归方法。以下是一个将其应用于打印深层嵌套表的示例：https://stackoverflow.com/a/42062321/5113346

我的版本使用您的输入示例产生相同的输出： 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5。

如果适用于其他传递参数，请原谅我，因为我没有尝试解决练习的答案，而是只是按照您的原始帖子重新编写了代码。