Is there a problem that has only a recursive solution? [duplicate]

Question

Possible Duplicates:
Is there a problem that has only a recursive solution?
Can every recursion be converted into iteration?
“Necessary” Uses of Recursion in Imperative Languages

Is there a problem that has only a recursive solution, that is, a problem that has a recursive solution, but an iterative solution has yet to be found, or better yet, has proven to be non-existing (obviously, this is not a tail-recursion)?

Answer 1

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.