Can all iterative algorithms be expressed recursively?

开发者_StackOverflow

If not, is there a good counter example that shows an iterative algorithm for which there exists no recursive counterpart?

If it is the case that all iterative algorithms can be expressed recursively, are there cases in which this is more difficult to do?

Also, what role does the programming language play in all this? I can imagine that Scheme programmers have a different take on iteration (= tail-recursion) and stack usage than Java-only programmers.

---

There's a simple ad hoc proof for this. Since you can build a Turing complete language using strictly iterative structures and a Turing complete language using only recursive structures, then the two are therefore equivalent.

---

Can all iterative algorithms be expressed recursively?

Yes, but the proof is not interesting:

1. Transform the program with all its control flow into a single loop containing a single case statement in which each branch is straight-line control flow possibly including break, return, exit, raise, and so on. Introduce a new variable (call it the "program counter") which the case statement uses to decide which block to execute next.

   This construction was discovered during the great "structured-programming wars" of the 1960s when people were arguing the relative expressive power of various control-flow constructs.

2. Replace the loop with a recursive function, and replace every mutable local variable with a parameter to that function. Voilà! Iteration replaced by recursion.

This procedure amounts to writing an interpreter for the original function. As you may imagine, it results in unreadable code, and it is not an interesting thing to do. However, some of the techniques can be useful for a person with background in imperative programming who is learning to program in a functional language for the first time.

---

Like you say, every iterative approach can be turned into a "recursive" one, and with tail calls, the stack will not explode either. :-) In fact, that's actually how Scheme implements all common forms of looping. Example in Scheme:

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

Here, although the function looks iterative, it actually recurses on an internal lambda that takes three parameters, x, y, and i, and calling itself with new values at each iteration.

Here's one way that function could be macro-expanded:

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

This way, the recursive nature becomes more visually apparent.

---

Defining iterative as:

function q(vars):
  while X:
    do Y

Can be translated as:

 function q(vars):
    if X:
      do Y
      call q(vars)

Y in most cases would include incrementing a counter that is tested by X. This variable will have to be passed along in 'vars' in some way when going the recursive route.

---

As noted by plinth in the their answer we can construct proofs showing how recursion and iteration are equivalent and can both be used to solve the same problem; however, even though we know the two are equivalent there are drawbacks to use one over the other.

In languages that are not optimized for recursion you may find that an algorithm using iteration preforms faster than the recursive one and likewise, even in optimized languages you may find that an algorithm using iteration written in a different language runs faster than the recursive one. Furthermore, there may not be an obvious way of written a given algorithm using recursion versus iteration and vice versa. This can lead to code that is difficult to read which leads to maintainability issues.

---

Prolog is recursive only language and you can do pretty much everything in it (I don't suggest you do, but you can :))

---

Recursive Solutions are usually relatively inefficient when compared to iterative solutions. However, it is noted that there are some problems that can be solved only through recursion and equivalent iterative solution may not exist or extremely complex to program easily (Example of such is The Ackermann function cannot be expressed without recursion)Though recursions are elegant,easy to write and understand.