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

that depends what you call recursive. every recursive function can be translated to a non-recursive one by implementing a stack.. — yairchu, Jul 07 '09 at 20:36
Yes; it is described in detail here: http://stackoverflow.com/questions/1094679/ — Marc Gravell, Jul 07 '09 at 20:37
@Marc Gravell:Brilliant, we can find the same thing when looking at the index for Recursion in the K&R. (The index references a bunch of pages and the index page...) — LB40, Jul 07 '09 at 20:58
Another dupe: http://stackoverflow.com/questions/1011448/necessary-uses-of-recursion-in-imperative-languages — ShreevatsaR, Jul 07 '09 at 21:11
I think that's more of "do any problems exist where iteration is terribly bad compared to recursion" rather that "are there problems that absolutely require recursion" — GManNickG, Jul 07 '09 at 21:13
I thin series like Fibonacci ones (https://en.wikipedia.org/wiki/Fibonacci_number) are good candidates for algorithms that can be solved only recursively. — Hardest, Jan 12 '19 at 16:02
I think the question here is not if a recursive algorithm can be always translated in an iterative algorithm (and the answer is YES [1]). The question was: does it exist a class of problems which formulation can be expressed only with recursion? And also for this the answer is yes. For example to determine if a certain sequence of numbers is present in the infinite expansion of the Pi number [2]. [1] https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration [2] https://mathoverflow.net/questions/23547/does-pi-contain-1000-consecutive-zeroes-in-base-10 — Hardest, Jan 12 '19 at 16:31

Jimmy · Answer 1 · 2009-07-08T06:29:37.620

19

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.

edited Jul 08 '09 at 06:29

answered Jul 07 '09 at 20:34

Jimmy

89,068
17
119
137

2

That is not recursion elimination. When one replace recursive function with non-recursive one it is supposed to use limited memory instead of theoretically unlimited stack. – Kirill V. Lyadvinsky Jul 07 '09 at 20:43
3

"Guaranteed to use a finite amount of memory" is not the definition of a nonrecursive function. It might be a desirable property, but it's not a definitional requirement. An iterative algorithm with a memory leak will use a potentially unlimited amount of memory, but nobody would argue that alone makes the algorithm recursive. – Chuck Jul 07 '09 at 21:10
2

@jia3ep: this is recursion elimination. in fact, it already has a tangible benefit in some situations by moving the load from the operating system's call stack (which in many architectures has a limited space) into the heap, and avoiding the overhead of a function call. – Jimmy Jul 07 '09 at 21:44
This doesn't change the idea of the recursion in my opinion, you can as well implant a virtual machine in some non-stack way, and run your recursion code on top of it, I was thinking more in the spirit of a different algorithm. nice idea nonetheless. – Liran Orevi Jul 08 '09 at 04:06
@Jimmy, Hardware stack is much faster then using heap, so stack emulation has no obvious advantage. – Kirill V. Lyadvinsky Jul 08 '09 at 04:24
I think the quetion here is not if a recursive algorithm can be always translated in an iterative algorithm (and the answer is YES [1]). – Hardest Jan 12 '19 at 16:23

score 14 · Answer 2 · edited May 23 '17 at 12:09

14

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

edited May 23 '17 at 12:09

Community

1
1

answered Jul 08 '09 at 00:28

Jimmy

89,068
17
119
137

I assume the 'append' is really a 'push'? – Erich Mirabal Jul 08 '09 at 04:19
well, this is a list in python heh. – Jimmy Jul 08 '09 at 05:59
How does it compare between the non-recursive impl and recursive impl compare? In other words, is there a performance or readability improvement to using recursion? – Aaron Hull Dec 14 '22 at 08:41

score 9 · Accepted Answer · edited Dec 11 '20 at 17:00

9

The Ackermann function cannot be expressed without recursion

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

edited Dec 11 '20 at 17:00

Tim

6,265
5
29
24

answered Jul 07 '09 at 20:41

LB40

12,041
17
72
107

+1. Nice. I think this is about the only real answer on here (well, besides Marc's comment). – Erich Mirabal Jul 07 '09 at 20:51
14

Counter: "The Ackermann function can also be expressed nonrecursively using Conway chained arrow notation" (see wikipedia) – Marc Gravell Jul 07 '09 at 21:05
and "hyper operators" and "the indexed version of Knuth's up-arrow notation" – Marc Gravell Jul 07 '09 at 21:06
I thought it was just a shortcut to recursion but still recursion... – LB40 Jul 07 '09 at 21:19
4

Interesting. The Ackermann function is not a primitive recursive function: http://en.wikipedia.org/wiki/Primitive_recursive_function. According to this page, a language with basic arithemetic, comparison, and bounded for-loops can't express this type of function. But if you add in WHILE or GOTO you're Turing-complete again. – Erika Jul 07 '09 at 21:21
2

see my response at http://stackoverflow.com/questions/1094679/is-there-a-problem-that-has-only-a-recursive-solution/1095538#1095538 – Jimmy Jul 08 '09 at 00:28
Weisstein, Eric W. "Primitive Recursive Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PrimitiveRecursiveFunction.html – Liran Orevi Jul 08 '09 at 03:52
6

I think it's important to differentiate between problems whose "mathematical" definition involves a recursive form ... vs. whose computation can only be achieved recursively. You can compute the Ackermann function using non-recursive programming form - however you _will_ to store state for each iteration. – LBushkin Jul 08 '09 at 12:42
1

@LBushkin I fully agree – LB40 Jul 08 '09 at 13:41
So, would you say that "Any problem that can be solved recursively can also be solved iteratively" is false? – Aaron Franke Mar 26 '18 at 05:03

score 8 · Answer 4 · answered Jul 07 '09 at 20:50

8

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

answered Jul 07 '09 at 20:50

Erika

653
6
11

in computational linguistics, the Turing Machine is above the Stack based automatas because it can emulate those (the strip can be used as a stack) – fortran Jul 07 '09 at 21:07

LBushkin · Answer 5 · 2009-07-08T12:44:35.783

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.

score 4 · Answer 6 · answered Jul 07 '09 at 20:33

4

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.

answered Jul 07 '09 at 20:33

Matthew Vines

27,253
7
76
97

1

So can the NP-complete ones. It just takes longer. – Ian Aug 15 '10 at 11:54
1

This answer is wrong. Undecidable problems are not NP-Complete (and they cannot be solved with iteration or recursion). – Paul Aug 30 '12 at 13:42

score 3 · Answer 7 · answered Jul 07 '09 at 20:36

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.

answered Jul 07 '09 at 20:36

ist_lion

3,149
9
43
73

Search in a tree can be Depth-first or Breadth-first. The former is naturally translated with recursion, but the later is more natural to implement with an iterative method. – David Rodríguez - dribeas Jul 07 '09 at 20:55

score 1 · Answer 8 · answered Jul 07 '09 at 20:38

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.

Is there a problem that has only a recursive solution?

8 Answers8

Linked