[This page is auto-generated; please prefer to read the article’s PDF Form.]
One way to create iterative variants of these recursive methods is to just simulate the recursive calls exactly as they would happen on the program-stack, but using our own stack. Our stack can maintain its elements to represent the recursive invocations similar to how program-stack maintains the call-frames. New elements will be pushed to simulate each recursive call, and the topmost element will be popped when a call returns. The elements (representing invocations) in our stack will pass through each of their resume-points as they execute. These resume-points can be stored as a number within each stack element, to indicate where to resume the execution. In an earlier article, Maintaining the Stack for Recursion, we had discussed about simulating a general recursive method on an stack.
But as we will see below, we can do some optimizations according to the specific traversal, and need not make an invocation element pass through all the resume-points. We will also derive the resume-point of an element as needed, instead of storing it.
Now, having understood some general details, we will go through each traversal individually.
Copyright © 2020 Nitin Verma. All rights reserved.