Converting a iterative algorithm to recursive

Question

I have writing a code to print the tree in Level Order using a queue(Array).

    void printLevelOrder(node *root) {
         node* queue[10];
         node*t=root;
         int y=0;
         queue[y]=t;
         for(int i=0;i<10;i++)
         {
                 printf("%d,",queue[i]->val); 

                 t=queue[i];
                 if((t->left)!=NULL){
                 queue[++y]=t->left;
                 }
                 if((t->right)!=NULL){
                 queue[++y]=t->right;
                 }
         } 
}

I want to convert the method into a recursive method. I tried but I am not getting the correct solution. Is it possible to convert this type of problem to using recursive calls?

I haven't seen a Level Order Traversal's recursive version. But it would be nice to see if someone come up with one. — Nishant
– Nishant, Commented Oct 9, 2012 at 7:25
There is a theorem stating that each iterative algorithm can be converted to recursive and vice versa. If that makes sense is another question. — Ivaylo Strandjev
– Ivaylo Strandjev, Commented Oct 9, 2012 at 7:58

Qnan · Accepted Answer · 2012-10-09 08:14:21Z

1

It is possible to make this recursive, but in this case the result would probably look like the body of the loop in the code above executing and then calling itself for the next element in the queue. It is not possible to convert this into a kind of recursion more often found in tree traversal algorithms, where the recursive method invokes itself for the child nodes of the one it received as an argument. There is thus no performance gain to expect -- you'll still need the queue or some structure like this -- and I don't really see the point in performing the conversion.

answered Oct 9, 2012 at 8:14

Qnan

3,74421 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Aman Deep Gautam · Accepted Answer · 2012-10-09 13:37:22Z

0

I am not sure if this is what you were looking for but it is partial recursion.

void print_level_part(node* p, level) {
    if(p) {
        if(level==1) {
            printf("%d", p->val);
        } else {
            print_level_part(p->left, level-1);
            print_level_part(p->right, level-1);
        }
    }
}

//the loop in main which does the main printing.
for(int i=0; i<n; ++i) {
    print_level_part(root, i);
}

If you want completely recursive solution then I may suggest that you change the for loop in main a recursive function.

answered Oct 9, 2012 at 13:37

Aman Deep Gautam

8,86722 gold badges80 silver badges136 bronze badges

Comments

Vaughn Cato · Accepted Answer · 2012-10-09 14:25:38Z

0

This is an example of what Qnan was talking about:

void printNext(node **queue,int i,int y)
{
  if (i==y) return;

  node *t = queue[i++];
  printf("%d,",t->val);

  if (t->left)  queue[y++] = t->left;
  if (t->right) queue[y++] = t->right;

  printNext(queue,i,y);
}

void printLevelOrder(node *root)
{
  node *queue[10]; /* be careful with hard-coded queue size! */
  int y=0, i=0;

  queue[y++]=root;
  printNext(queue,i,y);
  printf("\n");
}

answered Oct 9, 2012 at 14:25

Vaughn Cato

64.5k5 gold badges87 silver badges135 bronze badges

Comments

penelope · Accepted Answer · 2012-10-09 14:53:07Z

As far as I understand, printing a tree in "Level Order" is actually a BFS traversal of the given tree, for which the recursion is not suited. Recursion is a well-suited approach to DFS.

The recursion internally works with a stack (a LIFO structure), while BFS uses a queue (a FIFO structure). A tree algorithm is suitable for recursion if the solution for a root depends on (the results, or just traversal order) the solutions for the subtrees. Recursion goes to the "bottom" of the tree, and solves the problem from bottom upwards. From this, pre-order, in-order and post-order traversals can be done as recursions:

pre-order : print the root, print the left subtree, print the right subtree
in-order : print the left subtree, print the root, print the right subtree
post-order: print the left subtree, print the right subtree, print the root

Level-order, however, can not be decomposed in "do something for the root, do something for each of the subtrees". The only possible "recursive" implementation would follow @Qnan suggestion, and, as he said, would not make much sense.

What is possible, however, is to transform any recursive algorithm in to an iterative one fairly elegantly. Since the internal recursion actually works with a stack, the only trick in this situation would be to use your own stack instead of the system one. Some of the slight differences between this kind of recursive and iterative implementation would be:

with iterative, you save time on function calls
with recursive, you usually get a more intuitive code
with recursive, extra memory gets allocated for a return address with each function call
with iterative, you allocate the memory, and you determine where the memory is allocated

Collectives™ on Stack Overflow

Converting a iterative algorithm to recursive

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related