How do you remove recursion using stacks?

Answer 1

Using stacks won't remove recursion, they can only re-implement those recursions. In some cases we don't actually need a stack to implement a recursive algorithm, in which case an iterative implementation will typically perform better with little to no cost in additional memory. But if we require a stack in order to implement recursions iteratively, then we pay the cost in terms of additional memory consumption (the "built-in" call stack is fixed-size and exists whether we use it or not). In addition, there may be a performance cost if we cannot determine how much additional memory we need.

As an example, consider the recursive quicksort algorithm:

template<typename T>using iter = std::vector<T>::iterator; template<typename T>void quicksort (iter begin, iter end) {

if (begin<end) {

size_t pivot = partition (begin, end);

quicksort (begin, pivot - 1);

quicksort (pivot + 1, end);

} // end if

}

Note that the partition algorithm is not shown for the sake of brevity. However, it is best implemented as a separate function as its local variables play no part in the recursion.

Being a divide-and-conquer algorithm, this algorithm requires a stack for back-tracking. Here is the iterative equivalent using a stack:

template<typename T>using iter = std::vector<T>::iterator;

template<typename T>void quicksort (iter begin, iter end) {

if (begin<end) {

std::stack<std::pair<iter, iter>> s {};

s.push ({begin, end});

while (s.empty() == false) {

begin = s.top().first();

end = s.top().second();

s.pop();

size_t pivot = partition (begin, end);

if (pivot + 1<end) s.push ({pivot + 1, end});

if (begin<pivot - 1) s.push ({begin, pivot - 1});

} // end while

} // end if

}

Note that the order we push the pairs on at the end of the while loop is the reverse order we wish them to be processed. The order doesn't actually matter, but it ensures both algorithms operate in a consistent manner, with depth-first traversal from left to right.

This implementation is naive because each push allocates new memory for each pair object we push onto the stack, releasing the same memory with each pop. Allocating and releasing system memory on a per-element basis like this is highly inefficient, so it's highly unlikely that this version will perform any better than the recursive algorithm.

However, the quicksort algorithm guarantees that there can never be more elements on the stack than there are elements in the initial range, so we can improve performance significantly by reserving sufficient memory in advance:

template<typename T>using iter = std::vector<T>::iterator;

template<typename T>void quicksort (iter begin, iter end) {

if (begin<end) {

std::vector<std::pair<iter, iter>> v {};

v.reserve (end - begin);

v.emplace_back (begin, end);

while (v.empty() == false) {

begin = v.back().first();

end = v.back().second();

v.pop_back();

size_t pivot = partition (begin, end);

if (begin < pivot - 1) v.emplace_back (begin, pivot - 1);

if (pivot + 1 < end) v.emplace_back (pivot + 1, end);

} // end while

} // end if

}

Note that in this implementation we use a vector rather than a stack, however all pops and pushes (implemented as emplace_back operations) occur at the back of the vector where the unused elements are, and that's precisely how an efficient stack should be implemented. As a result, this version will perform significantly better than the previous version and should perform at least as well as the recursive implementation if not better. The only significant cost is the cost of reserving memory in the vector.