Is there a problem that has only a recursive solution?

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

All non np-complete problems can be solved with just sequence, decision, and iteration. Recursion should not be required, though it usually greatly simplifies the problem.

Answer 2

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.

Answer 3

It comes down to how many lines of code is it going to take to solve the problem...

List all the files on your C:\ using recursion and then without. Sure you can do it both ways - but one way is going to be a lot simpler to understand and debug.

Answer 4

No. Recursion is nothing more than a stack and you can achieve the same results by implementing a stack explicitly.

That may not be an especially satisfying answer, but you'd have to ask a much more specific question to get a better answer. For example, theory dictates that in the levels of computing there is quite a difference in the range of problems that can be solved if you have a while loop vs. only having (traditional) for loops.

I put "traditional" in there because they really mean loops that iterate a certain number of times whereas C style for (...;...;...) loops are while loops in disguise.

Answer 5

In programming, recursion is really a special case of iteration - one where you use the call stack as a special means of storing state. You can rewrite any recursive method to be an iterative one. It may be more complicated or less elegant, but it's equivalent.

In mathematics, there are certain problems that require recursive techniques to arrive at an answer - some examples are finding roots (Newton's Method), computing primes, graph optimization, etc. However, even here, there's just a question of how you differentiate between the terms "iteration" and "recursion".

EDIT: As others have pointed out, there exist many functions whose definition is recursive - ex. the Ackermann function. However, this does not mean that they cannot be computed using iterative constructs - so long as you have a turing complete operation set and unlimited memory.

Answer 6

The Ackermann function cannot be expressed without recursion

Answer 7

You can define a Turing Machine without recursion (right?) So recursion isn't required for a language to be Turing-complete.

Answer 8

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