GofPatterns Gofpatterns





Behavioral Patterns  «Prev  Next»

Externalize the Stack Pattern

Intent:
Rewrite a recursive program/algorithm/function into an iterative one which uses an external stack.
Problem
All computer scientists are familiar with recursion and many consider it an alternative way of implementing iteration. Algorithms that use iteration must repeat some computation.
However, recursive algorithms, when written with the consideration of performance, can consume a valuable resource, namely theStack.
In languages which use stacks to maintain activation records, which include
  1. C ,
  2. C++, and
  3. Java
not including Smalltalk.
Some recursive algorithms exhibit TailRecursion and can be rewritten in an iterative way that uses bounded space (and some compilers, especially of functional languages, will perform this transformation as an optimization). However, many recursive algorithms are not tail-recursive.
The most natural way to express recursive algorithms is with recursive function calls; each instance of the function gets its own activation record to maintain its particular state, while TheStack holds the complete set.
The challenges with a Stack in many languages (or the stacks in multithreaded programs) are as follows:
In addition to holding the state which must be kept recursively, all other states (local variables) as well as tracking information for repeated function calls is held on the stack. Wastes memory. Would not be too much of a problem, except for...
Program stacks often must occupy contiguous address space. The remaining contiguous address space above the top of the stack is far less than the the total remaining system memory (physical and virtual). On many systems, the stack grows downward from the top of your address space.
Thus, the stack and the heap have exactly the same remaining memory available.


Solution
Figure out what state must be maintained between successive invocations of the function. Define a structure to hold that (and only that) state. Declare a stack (or a linked list, or whatever you have available) (a linked list is one possible implementation of the abstract data type stack, not something to be seen as an alternative to a stack) of that structure. Use it to hold the stacked copies of the recursive state. Then rewrite the remainder of the function to be iterative. In the case of Java serialization, and many other graph tree traversal algorithms, the only thing that needs to be maintained in recursive fashion is a BackPointer..