algorithm - 有人可以通过代码描述一个用迭代而不是递归回溯的实际例子吗？

Question

递归使回溯变得容易，因为它保证您不会再次走同一条路。因此，您路径的所有分支都只访问一次。我正在尝试将回溯尾递归(带累加器)算法转换为迭代。我听说将完美尾部递归算法转换为迭代应该很容易。但是我卡在了回溯部分。

任何人都可以通过代码提供示例，以便我自己和其他人可以直观地了解回溯是如何完成的吗？ 我认为这里不需要堆栈，因为我有一个使用累加器的完美尾递归算法，但我在这里可能是错的。

Answer 1

如果函数实际上是递归的，那么转换如下(这是理解 TCO 的编译器会为您做的，所以您不必自己做):

原文:

function func(a1, a2, a3...)
   ... doesn't contain either return or call
   return val
   ...
   return func(x1, x2, x3...)
   ...
   ... etc.

转换为:

function func(a1, a2, a3...)
   func:  // label for goto (yuk!)
     ...
     return val  // No change
     ...
     a1 = x1; a2 = x2; a3 = x3...; goto func;
     ...
     ... etc.

为了使这种转换与相互协同递归的函数一起工作，您需要将它们组合成一个函数，每个函数都带有一个标签。如上，简单的 return 语句没有改变，return foo(...) 变成对参数变量的赋值，然后是 goto foo。

当然，在组合函数时，可能需要重命名局部变量以避免冲突。并且您还将失去使用多个顶级函数的能力，除非您在顶级入口点添加类似 switch 语句(带有 gotos)，在任何标签之前。 (事实上​​，在允许 goto case foo 的语言中，您可以只使用 case 标签作为标签。)

goto 的使用当然是丑陋的。如果您使用的语言最好保证尾调用优化，或者失败了，至少做出合理的尝试并在失败时报告，那么绝对没有动力替换递归解决方案，这(在我看来)几乎总是更具可读性。

在某些情况下，可以用 while (1) { ... } 或其他类似的循环替换 goto 和 label ，但是这涉及将 goto 替换为 continue`(或等效项)，如果它们嵌套在其他循环中，则无法正常工作。因此，您实际上可能会浪费大量时间来使丑陋的转换稍微不那么丑陋，但最终仍无法获得与原始程序一样可读的程序。

我现在将停止宣传递归。 :)

已编辑(我没办法，抱歉)

这是 Lua 中的回溯 n 皇后解决方案(它确实执行 TCO)，由尾递归求解器和尾递归验证器组成:

function solve(legal, n, first, ...)
  if first == nil                    -- Failure
    then return nil
  elseif first >= n                  -- Back-track
    then return solve(legal, n, ...)
  elseif not legal(first + 1, ...)   -- Continue search
    then return solve(legal, n, first + 1, ...)
  elseif n == 1 + select("#", ...)   -- Success
    then return first + 1, ...
  else                               -- Forward
    return solve(legal, n, 0, first + 1, ...)
  end
end

function queens_helper(dist, first, second, ...)
  if second == nil
    then return true
  elseif first == second or first - dist == second or first + dist == second
    then return false
  else
    return queens_helper(dist + 1, first, ...)
  end
end

function queens_legal(...) return queens_helper(1, ...) end

-- in case you want to try n-rooks, although the solution is trivial.    
function rooks_legal(first, second, ...)
  if second == nil then return true
  elseif first == second then return false
  else return rooks_legal(first, ...)
  end
end

function queens(n) return solve(queens_legal, n, 0) end