Is there a characterization of algorithms that doesn't have a recursive form?

Question

This question arises from the binary tree representations(preorder, postorder, level order, etc.).Some of them can be written in a recursive form(preorder representation, for example), but I don't think there is a recursive algorithm for the level order representation(Or if you know how to do that please tell me!). So my question is: Is there a "type" of algorithms that cannot be written in recursive form? If so, how can this type of algorithms be characterized?(Or is there a system in which you can write a proof that certain algorithm cannot be written in a recursive way?)

Related: [Performing Breadth First Search recursively](https://stackoverflow.com/q/2549541/1639625) — tobias_k, Feb 08 '18 at 16:27
Loops and recursion are computationally equivalent. There is no algorithm that can be implemented recursively that cannot also be implemented iteratively, and vice versa. — chepner, Feb 08 '18 at 16:33
Yes, here's the full characterisation. The set of algorithms that cannot be expressed recursively is empty. — n. 1.8e9-where's-my-share m., Feb 08 '18 at 17:05

score 1 · Accepted Answer · answered Feb 08 '18 at 16:12

I don't necessarily think that this is a duplicate of this question, but it's a great reference. It provides a proof stating that every iterative algorithm can be written recursively. For that reason, there would be no category of algorithms which doesn't have a recursive form.

Yves Daoust · Answer 2 · 2018-02-08T16:39:27.893

0

while Condition do Statement end

can be equivalently written

to Perform():
    if Condition then Statement; Perform() end

and all sequential programs can be rewritten recursively, without loops.

edited Feb 08 '18 at 16:39

answered Feb 08 '18 at 16:19

Yves Daoust

53,540
8
41
94

Recursion is just your langauge's runtime maintaining a call stack for you. You can always replace recursion with iteration by maintaining that stack yourself. – chepner Feb 08 '18 at 16:32

score 0 · Answer 3 · answered Feb 08 '18 at 16:25

Recursion follows from a base case. If the final result follows from a base case then the algorithm has a recursive form. Recursive algorithms usually take the form F(n) = G( F(n-1 ) ... ) Example is Fibonacci series. F(n) = F(n-1) + F(n-2). This naturally falls into recursive form.

Your question seems to be more about implementation of an algorithm. Every recursive algorithm can be implemented both recursively and non-recursively. Because recursion inherently uses a function stack. The same stack you could use explicitly in the non-recursive form of implementation.

Therefore you could easily implement pre-order, post-order, in-order using both recursive and non-recursive forms.

Coming to level order, I am sure you could implement that in recursive form as well. For example ( may not be in its fully correct form ).

void printLevelOrder( int level, Queue<Node> q ) {

    if ( !q.isEmpty() ) {
      Node curr = q.peek();
      int size = q.size();
      System.out.print( "At level " + level + " : " );
      for ( int i = 0; i < size; i++ ) {
         System.out.println( q.poll().toString() );
      }
      for ( Node child : curr.children() ) {
        q.add( child );
      }
    }
    printLevelOrder( level + 1, q );
 }

But the point is implementation and mathematical form of algorithm are different.

Is there a characterization of algorithms that doesn't have a recursive form?

3 Answers3