Can someone describe through code a practical example of backtracking with iteration instead of recursion?

Question

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.

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.

From [wikipedia](http://en.wikipedia.org/wiki/Tail_call): `In computer science, a tail call is a subroutine call that happens inside another procedure as its final action`. As far as I know, a function with multiple recursive calls - is by definition not tail recursion, and since backtracking algorithms do have more then one call, they are not "tail recursive". — amit, Dec 08 '12 at 22:12
@amit: it doesn't matter how many places the function does the (recursive) call as long as all of them are the last action. (What "last action" means exactly depends on the language, but generally it's necessary that the call be of the form "return func(args...);" — rici, Dec 08 '12 at 22:49

rici · Answer 1 · 2012-12-09T02:29:07.327

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):

Original:

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

Converted to:

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.

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.)

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.

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)

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

Unless `P=NP`, it is impossible to convert a general case recursion (especially "multi called", (multiple invokations in each call)) into a loop + constant space. I elaborated on it as an [answer to the OPs previous question](http://stackoverflow.com/a/13782157/572670) (Note that if P=NP, it does not contradict the fact that it is impossible, but if P!=NP, it definetly is) — amit, Dec 08 '12 at 23:06
@amit, that's true, but such a recursion cannot be pure tail recursion, because in a tail recursion there is only one invocation in each call. There might be more than one invocation-point, but only one can be executed. Since the OP says tail-recursion, I think that the "general case recursion" issue is not relevant. — rici, Dec 08 '12 at 23:10
I guess I fail to understand how a (non trivial) backtracking algorithm can also be tail recursive. My intuition tells me there is none, so any answer is basically vacuous true :| — amit, Dec 08 '12 at 23:13
@amit: in accumulation style, you pass an accumulator and return it when you reach the end condition. To make this work with backtracking, you instead pass a list of accumulators; on failure, you tail-recurse, dropping the head of the list. At a backtrack point, you tail-recurse with a new accumulator pushed onto the head of the list. — rici, Dec 08 '12 at 23:16
This is basically equivalent to a stack + loop, which from what I understand is NOT what the OP is after :| — amit, Dec 08 '12 at 23:19
@amit, the OP says "I have a perfectly tail-recursive algorithm". I can only take that to mean that the OP has a perfectly tail-recursive algorithm. — rici, Dec 08 '12 at 23:41
It was my bad. See the chosen best answer here: http://stackoverflow.com/questions/13782136/can-a-backtracking-tail-recursive-algorithm-be-converted-to-iteration — chrisapotek, Dec 08 '12 at 23:45
@amit, fwiw, I added a tail-recursive back-tracking n-queens solution, for your viewing pleasure. — rici, Dec 09 '12 at 02:14
@chrisapotek, see addendum to answer, in case you're interested in what a back-tracking tail-recursive algorithm looks like — rici, Dec 09 '12 at 02:15

Can someone describe through code a practical example of backtracking with iteration instead of recursion?

1 Answers1

Linked