Recursion

Recursion is likely the most famous functional programming technique. If you don't know by now, a recursive function is a function that calls itself.

When a functions calls itself, something strange happens. It acts both as a loop, in that it executes the same code multiple times, and as a function stack.

Recursive functions must be very careful to avoid an infinite loop (rather, infinite recursion in this case). So just like loops, a condition must be used to know when to stop. This is called the base case.

An example is as follows:

var foo = function(n) {   if (n < 0) {     // base case     return 'hello';   }   else {     // recursive case     foo(n-1);   } } console.log(foo(5));

It's possible to convert any loop to a recursive algorithm and any recursive algorithm to a loop. But recursive algorithms are more appropriate, almost necessary, for situations that differ greatly from those where loops are appropriate.

A good example is tree traversal. While it's not too hard to traverse a tree using a recursive function, a loop would be much more complex and would need to maintain a stack. And that would go against the spirit of functional programming.

var getLeafs = function(node) {   if (node.childNodes.length == 0) {     // base case     return node.innerText;   }   else {     // recursive case:      return node.childNodes.map(getLeafs);   } }

Divide and conquer

Recursion is more than an interesting way to iterate without for and while loops. An algorithm design, known as divide and conquer, recursively breaks problems down into smaller instances of the same problem until they're small enough to solve.

The historical example of this is the Euclidan algorithm for finding the greatest common denominator for two numbers.

function gcd(a, b) {   if (b == 0) {     // base case (conquer)     return a;   }   else {     // recursive case (divide)     return gcd(b, a % b);   } }  console.log(gcd(12,8)); console.log(gcd(100,20));

So in theory, divide and conquer works quite eloquently, but does it have any use in the real world? Yes! The JavaScript function for sorting arrays is not very good. Not only does it sort the array in place, which means that the data is not immutable, but it is unreliable and inflexible. With divide and conquer, we can do better.

The merge sort algorithm uses the divide and conquer recursive algorithm design to efficiently sort an array by recursively dividing the array into smaller sub-arrays and then merging them together.

The full implementation in JavaScript is about 40 lines of code. However, pseudo-code is as follows:

var mergeSort = function(arr){   if (arr.length < 2) {     // base case: 0 or 1 item arrays don't need sorting     return items;   }   else {     // recursive case: divide the array, sort, then merge     var middle = Math.floor(arr.length / 2);     // divide     var left = mergeSort(arr.slice(0, middle));     var right = mergeSort(arr.slice(middle));     // conquer     // merge is a helper function that returns a new array     // of the two arrays merged together     return merge(left, right);   } }