Can any recursion implementation be written as tail-recursion?
You can't rewrite all your recursive calls as tail recursive calls but you can rewrite your program in continuation passing style which is closely related and has the feature that every procedure call is a tail call (just not necessarily a tail recursive call.)

The way you do this is by recognizing that every time you make a procedure call you are implicitly specifying a return point.  Then you split your procedure into multiple procedures, each starting at a return point and ending at the next call point.  Continuation-passing style essentially makes the stack explicit.  Once the stack is explicit it is easier to apply certain optimization (like tail recursion elimination).

Example

procedure depth_first(t):
  if not-null(t):
    l = depth_first(t-&gt;left)
    r = depth_first(t-&gt;right)
    return l + r + 1
  else:
    return 0


The first step is to make every procedure take an extra parameter, k which is a continuation procedure (a procedure which you return to by calling it with the return value as its parameter).  Then you turn the procedure "inside out":

procedure depth_first(t, k):
  if not-null(t):
    depth_first(t-&gt;left,
       lambda(l):
         depth_first(t-&gt;right,
           lambda(r):
             k(l + r + 1)
  else:
    k(0)


Should you do it?  Well, if you're a compiler and you want to perform tail-recursion elimination optimizations, or generate machine code, then yes.  Otherwise probably not.  One of the joys of high level languages is that they have syntax that makes continuations much easier for humans to read and understand.  Let the compiler do what it's best at and concentrate on writing maintainable code.