Externalize the Stack Pattern

How do I rewrite a recursive program or function into an iterative program using an external stack?
Converting a recursive program or function into its iterative counterpart often involves utilizing an external data structure, commonly a stack, to emulate the call stack behavior exhibited by the recursive approach. This transformation is often referred to as "removing the recursion" or "manual tail recursion." Let's delve into this transformation process step by step:

1. Understand the Recursive Approach:
   
   1. Begin by comprehensively understanding the recursive logic. Identify the base case(s) and the recursive case(s).
   2. Recognize the parameters and local variables involved in the recursive calls.
2. Set Up the External Stack:
   
   1. Instantiate an external stack to store the state information required for each level of the recursive call.
   2. This stack will typically hold parameters, local variables, and possibly other information necessary to emulate the recursive call's behavior.
3. Initialization: Push the initial state or parameters (those you would have passed to the recursive function) onto the stack.
4. Iterative Process:
   
   1. Use a loop that continues as long as the stack is not empty.
   2. Within the loop, `pop` the current state from the top of the stack.
   3. If the current state corresponds to a base case in the recursive logic, process it accordingly.
   4. If the current state corresponds to a recursive case, push any new state(s) that result from the recursive call(s) onto the stack. This might involve pushing multiple new states if there are multiple recursive calls within the function.
5. State Management:
   Carefully manage the state within the loop. This involves not only parameters passed to the recursive calls but also any local variables or intermediate results. Consider using a structured approach, perhaps by defining a class or a struct (depending on the programming language), to group together all the information that needs to be stored on the stack for each state.
6. Return and Output:
   If the original recursive function returned a value, you'll need to determine how to compute and return this value iteratively. Sometimes, this can be done by maintaining an accumulator or another external variable to aggregate results as the stack is processed.

Consider a simple recursive function to compute factorial:

def factorial_recursive(n):
    if n == 0:
        return 1
    else:
        return n * factorial_recursive(n-1)

To convert this into an iterative approach using a stack:

def factorial_iterative(n):
    stack = []
    result = 1

    while True:
        if n > 1:
            stack.append(n)
            n -= 1
        elif stack:
            n = stack.pop()
            result *= n
            n -= 1
        else:
            break

    return result

In this iterative approach, the external stack keeps track of the numbers we still need to multiply to compute the factorial. As you can see, the logic of the recursive method is retained but is expressed in an iterative manner.
Transforming a recursive function into an iterative one using an external stack can be a powerful technique, especially when handling cases where recursion depth might lead to a stack overflow. However, it demands careful management of state and a deep understanding of the recursive logic being emulated.

Rewrite a recursive program/algorithm/function into an iterative one which uses an external stack.

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 the following fact. 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.

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, which is a pointer to the previous node.