Home

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Recursion as Tree Traversal

The recursive execution of recur() corresponds to a binary tree where each node represents a call (with its args-tuple) and its two child nodes represent the two recursive calls. The root node is the initial call. Consider the inorder traversal of this tree in which, upon a node’s visit (processing), we perform the move step of its call. We can reason that, the move steps thus performed will be same as those performed by the complete execution of the initial call.

In recur2() and nonrecur() also, the same inorder traversal of the tree takes place. There, the nodes (args-tuples) are generated on-the-fly by using transformations between parent and child nodes. But once we visit a node (do its move step), we will often end-up performing multiple such transformations before we obtain and visit its successor node (do we see why?). (In inorder traversal, successor of a node is the node visited just after it).

B. Meyer makes some interesting observations about how a node and its successor are related, and how the successor can be obtained directly from a node by a simple transformation [2]. Thus, the same inorder traversal can be performed but while directly obtaining and visiting the successor node after each node. This saves the multiple intermediate transformations (between parent-child nodes) we did above.

■

References

[Prev]   [Up]   

Copyright © 2021 Nitin Verma. All rights reserved.