有人可以通过codeA的实用性和迭代，而不是递归回溯的例子说明？ [英] Can someone describe through code a practical example of backtracking with iteration instead of recursion?

问题描述

递归使得回溯容易，因为它保证你不会经历相同的路径了。所以，你的路径的所有后果都访问一次。我想一个回溯尾递归（带蓄电池）算法转换为迭代。我听说它应该很容易转换完美的尾部 -recursive算法进行迭代。但我被困在回溯部分。

Recursion makes backtracking easy as it guarantees that you won't go through the same path again. So all ramifications of your path are visited just once. I am trying to convert a backtracking tail-recursive (with accumulators) algorithm to iteration. I heard it is supposed to be easy to convert a perfectly tail-recursive algorithm to iteration. But I am stuck in the backtracking part.

任何人都可以提供一个例子，通过code所以我和其他人可以直观地了解回溯做？ 我认为是不需要的堆栈在这里，因为我有一个完美的尾递归算法使用蓄电池，但我可以在这里是错误的。

Can anyone provide a example through code so myself and others can visualize how backtracking is done? I would think that a STACK is not needed here because I have a perfectly tail-recursive algorithm using accumulators, but I can be wrong here.

推荐答案

如果该功能实际上是递归的，那么改造如下（这就是它理解TCO会为你做，所以你应该不是一个编译器必须做你自己）：

If the function is actually recursive, then the transformation is as follows (and this is what a compiler which understand TCO will do for you, so you shouldn't have to do it yourself):

原文：

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.

为了使与相互配合的递归函数这一转变的工作，你需要将它们组合成一个单一的功能，每一个都带有一个标签。如上所述，简单的返回语句没有改变，而返回富（...）变成分配到参数变量其次是转到富。

In order to make this transformation work with mutually co-recursive functions, you need to combine them into a single function, each of which comes with a label. As above, simple return statements are not altered, and return foo(...) turn into assignment to parameter variables followed by goto foo.

当然，在组合功能，您可能需要重命名局部变量，以避免冲突。而你也将失去使用一个以上的顶级功能，除非你购买的东西就像一个开关语句（与 GOTO S）在顶部入口点，任何标签之前。 （事实上​​，在语言中，允许转到例中foo ，你可以只使用的情况下标签为标签。）

Of course, when combining the functions, you may need to rename local variables to avoid conflicts. And you will also lose the ability to use more than one top-level function, unless you add something like a switch statement (with gotos) at the top entry point, before any label. (In fact, in a language in which allowed goto case foo, you could just use the case labels as labels.)

使用 GOTO 的是，当然，难看。如果您使用的美元语言p $ pferably保证尾调用优化，或做不到这一点，至少使一个合理的尝试做到这一点，当它失败时的报告，那么就绝对没有动机来代替递归解决方案，这（在我的意见）几乎总是更具有可读性。

The use of goto is, of course, ugly. If you use a language which preferably guarantees tail-call optimization, or failing that, at least makes a reasonable attempt to do it and reports when it fails, then there is absolutely no motivation to replace the recursive solution, which (in my opinion) is almost always more readable.

在某些情况下，它可以用类似于替换 GOTO 和标签，而（1） {。 ..} 或其他这样的循环，但涉及与 continue`（或同等学历）替换转到 s和如果他们嵌套在其他循环内，将无法正常工作。所以，你实际上可以浪费了不少时间做丑陋的转变略少丑，还没有最终有一个程序的可读性与原始。

In some cases, it's possible to replace the goto and label with something like while (1) { ... }or other such loops, but that involves replacing thegotos withcontinue` (or equivalent), and that won't work if they're nested inside of other loops. So you can actually waste quite a lot of time making the ugly transformation slightly less ugly, and still not end up with a program as readable as the original.

我会停下来传教递归。 :)

I'll stop proselytizing recursion now. :)

编辑（我不能帮助它，对不起）

Edited (I couldn't help it, sorry)

下面是Lua中（它做TCO）一回跟踪N皇后的解决方案，其中包括一个尾递归求解器和一个尾递归验证的：

Here's a back-tracking n-queens solution in Lua (which does do TCO), consisting of a tail-recursive solver and a tail-recursive verifier:

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

这篇关于有人可以通过codeA的实用性和迭代，而不是递归回溯的例子说明？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！