1

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

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

4

1 回答 1

0

如果函数实际上是递归的，那么转换如下（这是理解 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语句（带s）的东西。goto（事实上​​，在允许的语言中goto case foo，您可以只使用大小写标签作为标签。）

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

在某些情况下，可以将gotoand 标签替换为while (1){ ... } or other such loops, but that involves replacing thegoto s withcontinue`（或等效项）之类的东西，如果它们嵌套在其他循环中，这将不起作用。因此，您实际上可能会浪费大量时间来使丑陋的转换稍微不那么丑陋，但最终仍然无法获得像原始程序那样可读的程序。

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

已编辑（我忍不住，抱歉）

这是 Lua 中的一个回溯 n-queens 解决方案（确实有 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
于 2012-12-08T23:02:18.043 回答