Thinking Recursively With Code

tl;dr Algorithms written up in recursion are easier to grok. And even more fun to demo. Go for a test drive on repl.it by clicking here. Find the “run” button and let it rip!

“Recursive functions are confusing, elegant and fascinating, all at the same time!”

When it comes to grokking (understand something intuitively or by empathy) how sorting algorithms work, the cognitive load is far less when the algorithm is first approached in its recursive form. And even better, in English-like code. Let’s the take case of SelectionSort, one of the more basic sorting algorithms.

The Selection Sort Recursive Algorithm

1. Define the recursion termination condition by checking for an array of size zero.
2. Select (and therefore the namesake algorithm) the minimum value in the arrayToBeSorted (denoted by variable a).
3. Build a new array containing the minimum value alone, and remove it from the arrayToBeSorted.
4. To this new array, concatenate the output of the recursive call on the remainder of arrayToBeSorted.
5. And finally, return the array.

After a million refactors (of course, I exaggerate, only slightly), I came up with the following Javascript code which employs the quirky Array.prototype.splice() function. Surprisingly, the main recursive function required exactly three lines. It was as if splice and SelectionSort were made for each other!

// helper function that returns the index of the
// minimum value in the array 
function indexOfMinValue(arr){
    return arr.reduce((iMin, x, i) => x > arr[iMin]? iMin : i, -1);
}
function selectSortR(a){
  if (!a.length) return [];                     // #1, terminal case
  let minVal = a.splice(indexOfMinValue(a), 1); // #2 and #3 
  return minVal.concat(selectSortR(a));         // #4 and #5
}

“And, you call that English-like?” Well, sorry for the bait-and-switch. Let me make it up with some elaboration of the cryptic parts of the above code. I promise it won’t be long. After all, I only have 3 lines of code to explain!

Line 1 is about terminal case

if (!a.length) return []; 

For any recursive function to work, there has to be a terminal case. Otherwise, the function will continue for perpetuity.

Line 2 is about selection and removal

minVal = a.splice(indexOfMinValue(a), 1); 

This code is best explained with the help of an example. Consider an array containing [5, 8, 3, 9]. The function indexOfMinValue will return a value of 2 (because 3 being the smallest of the numbers and is located at index 2 of the array, i.e. a[2]). Therefore, the right-hand-side (RHS) of the above statement resolves to a.splice(2, 1).

Image courtesy: http://www.javascripttutorial.net/

The function splice mutates the array by selecting out exactly one element (the 2nd argument in the function is the value 1) starting at index 2, leaving the remaining elements in the array (a now containing [5, 8, 9]). An array containing the selected value (3) is assigned to the variable minVal.

At this point, we now have a selection (a.k.a. an array containing the minimum value), and therefore the name SelectionSort. This single line of Javascript code represents the core of the algorithm.

Line 3 is about combining and returning

return minVal.concat(selectSortR(a));

In the final line, the new array (minVal) is then ‘concat’enated with the return values of all subsequent function calls to selectionSortR with the argument a (sans the selected element ‘3’, then ‘5’, and so on). And finally, return the combined array containing the sorted elements.

Now, adding a logging statement (between Line #2 and Line #3) as given below to display the magic of recursion!

console.log(minVal, a); // to witness the magic of recursion

And so there it is:

3-line recursive Selection Sort

And finally, you must test drive the code and see how it plays out for yourself. Click this link here and modify the variable alist as you please. For the example used in the above code, the following is the output:

selectSort([5, 8, 3, 9])
[ 3 ] [ 5, 8, 9 ]
[ 5 ] [ 8, 9 ]
[ 8 ] [ 9 ]
[ 9 ] []
=> [ 3, 5, 8, 9 ]

I firmly believe grokking an algorithm in recursive code makes the learner a better thinker. Moreover, the learner is better equipped to grok the in-place, iterative versions of the same algorithm.

But, why bother? Well, the recursive versions of sorting algorithms, while elegant and simple, more often than not, perform poorly in comparison to their iterative in-place versions.