I have always intuitively shied away from using recursion in my code wherever possible. The few times I have had to implement it were mainly in some form of tree traversal logic. I am a little uncomfortable in relying on intuition, so in this post I’m going to flesh out my thoughts on recursion.

In certain scenarios a recursive implementation is very concise. Let’s take a look at a recursive Merge Sort:

void mergeSort(std::vector<int>& a, int l, int r) { if (l < r) { int m = (l+r)/2; mergeSort(a, l, m); mergeSort(a, m+1, r); merge(a, l, m, r); } }

This is very concise but the recursive logic calls are difficult to follow. The best representation of this I’ve found is this from geeksforgeeks.com:

This is quite elegant how the numbers get split up through the recursive calls and then get merged as the recursive calls unwind. It is however not intuitive by looking at the source code and requires some thought, thinking through the recursive call tree. The other disadvantage is the inherent limitations of recursive calls, i.e. the overhead of the recursive calls and stack size limit which limits the scalability for large data sets.

Lets compare this to an iterative implementation:

void merge_sort_iterative(std::vector<int>& nums) { int chunk_size = 1; //start merging one element at a time for ( ; chunk_size <= nums.size()-1; chunk_size*=2) { //iterate through this pass merging adjacent chunks for (int idx=0; idx<nums.size(); idx+=(chunk_size*2)) { int merge_size = chunk_size*2; if (nums.size()-idx < merge_size) merge_size = nums.size()-idx; if (merge_size==1) continue; merge_sort_combine(nums, idx, chunk_size); } } }

I’ve used more descriptive variable names and comments here, so the comparison is not completely fair. Both the recursive and iterative solutions rely on a merge function not shown, but these would have similar logic. The key difference is that the iterative is intuitively easier to understand as you don’t have to think through the recursive call tree.

It is interesting that most descriptions of merge sort default to a recursive implementation. I would argue that the iterative solution is easier to understand and implement. The recursive solution is an interesting learning exercise in the way the recursive call tree unravels.

In some cases implementing an iterative alternative to a recursive algorithm requires using a stack data structure. An example is an iterative version of a quick sort, which repeatedly pushes the two partition dimensions to a stack and then repeatedly pops elements off the stack and does a partition again:

void quicksort_iterative(std::vector<int>& nums, int l, int r) { std::stack<std::pair<int,int>> s; s.push({l,r}); while (s.size() > 0) { auto bounds = s.top(); s.pop(); int cur_l = bounds.first; int cur_r = bounds.second; if (cur_r-cur_l >= 1) { int i = partition(nums, cur_l, cur_r); s.push({cur_l,i-1}); s.push({i+1,cur_r}); } } }

So to summarise I would say recursive implementations, compared to iterative alternatives, tend to be:

– less intuitive

– less efficient

– less scalable