Is there a problem that has only a recursive solution?

replace function calls with pushing arguments onto a stack, and returns with popping off the stack, and you've eliminated recursion.

Edit: in response to "using a stack does not decrease space costs"

If a recursive algorithm can run in constant space, it can be written in a tail-recursive manner. if it is written in tail-recursive format, then any decent compiler can collapse the stack. However, this means the "convert function calls to explicit stack-pushes" method also takes constant space as well. As an example, lets take factorial.

factorial:

def fact_rec(n):
    ' Textbook Factorial function '
    if n < 2:  return 1
    else:      return n * f(n-1)


def f(n, product=1):
    ' Tail-recursive factorial function '
    if n < 2: return product
    else:     return f(n-1, product*n)

def f(n):
    ' explicit stack -- otherwise same as tail-recursive function '
    stack, product = [n], 1
    while len(stack):
        n = stack.pop()
        if n < 2: pass 
        else:
            stack.append(n-1)
            product *= n
    return product

because the stack.pop() follows the stack.append() in the loop, the stack never has more than one item in it, and so it fulfills the constant-space requirement. if you imagine using a temp variable instead of a 1-length stack, it becomes your standard iterative-factorial algorithm.

of course, there are recursive functions that can't be written in tail-recursive format. You can still convert to iterative format with some kind of stack, but I'd be surprised if there were any guarantees on space-complexity.

The Ackermann function cannot be expressed without recursion

edit: As noted in another answer, this is incorrect.

In Response to the Ackermann function answer, this is a pretty straightforward convert-the-call-stack-into-a-real-stack problem. This also shows one benefit of the iterative version.

on my platform (Python 3.1rc2/Vista32) the iterative version calculates ack(3,7) = 1021 fine, while the recursive version stackoverflows. NB: it didn't stackoverflow on python 2.6.2/Vista64 on a different machine, so it seems to be rather platform-dependant,

(Community wiki because this is really a comment to another answer [if only comments supported code formatting .... ])

def ack(m,n):
  s = [m]
  while len(s):
     m = s.pop()
     if m == 0:
        n += 1 
     elif n == 0:
        s.append(m-1)
        n = 1
     else:
        s.append(m-1)
        s.append(m)
        n -= 1
  return n