How to convert recursion algorithms into iteration version 1


In technical interviews, many candidates are asked to implement recursion algorithms using iteration. Generally, an algorithm implemented in iteration will run faster than that in recursion, since it avoids the overhead of function call. With the help of a stack and careful algorithm design, we can convert all recursion algorithms to its corresponding iteration version.

First, let’s start with a general recursion template code written in C++. It is a recursive traversal in binary tree.

There are three types of recursion, distinguished by the visiting order – preorder, postorder and inorder. In another word, we visit every node for three times. We may visit a node coming from its parent node (preorder), from its left child (inorder), or from its right child(postorder).

Untitled-1

Therefore, in the iteration code, we need to attach an attribute to each node indicating how many times we have visited this node. In our design, we use an integer to store this information and use an stack to simulate function call stack in system.

Following is the iteration version of previous recursion code. They are functionally equal.

It needs to be clarified that we need to push the right child first, then current node itself, and finally the left child, since elements in stack follow first-in-last-out order.

 

1
Leave a Reply

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of

[…] 参见:http://www.sunny-song.com/convert-recursion-algorithms-iteration-version/ […]