Recursion Made Simple

Recursion isn’t as hard as you think

Update: I’ve been hacking on Dilio as a side project, and guess how I’ve used recursion? I’ve written an intersperse function which isn’t available in TypeScript! Here it is:

function intersperse(src: Array<T>, arr: Array<T>, itemFunc: () => <T>): Array<T> {
  if (src.length <= 0) arr;
  arr.push(src.shift() || <T>{})
  arr.push(itemFunc());
  return intersperse(src, arr);
};

After you have finished reading, come back and try to rewrite this with a for loop to earn recursion wisdom mode!

What is recursion? Recursion is a very simple concept in programming, yet it is one of the most mathematically elegant and mesmerizing universal concepts. So many occurrence in nature bears a recursive pattern, such as the famous nautilus shells, sunflowers, and various plants. Even the universe might be recursive.

In functional programming, recursion is the core. In many cases, you cannot even iterate a list without it. Recursion is the art of induction — reducing a component and breaking it down to smaller and smaller components repetitively using the very same logic or function to solve each of them.

However, recursion stands to be one of the more difficult concepts to grasp (provided many programmers still have problems with fizzbuzz). I myself had been programming in Java, C++, Python, and Go, but recursion always seemed like a far-fetched impractical technique that’s rarely used in real life, which mostly consists of calling libraries’ methods with the right parameters in the right order and organizing code to make it run in a framework. In hindsight, that was barely programming. It was housekeeping.

However, I never truly understood recursion, not even when I had to prepare for technical interviews. I didn’t understand it even from gazillions of Fibonacci-style code examples. Most books and materials like to jump to talk about stacks early on, which made it even more cumbersome. No, it started to dawn on me when I started working with a functional language, by which I was not able to even get an element off a list without using recursion.

Therefore, here I am doing it differently by starting from something much simpler, like summing an array of integers, and doing it in JavaScript, a language anyone(?) can understand, yet functional enough to not suck in the face of recursion. There is an example in Ocaml, but it should be simple enough to follow.

Sum the numbers

Let’s say we have the following array consisting of integers from 1 to 5:

let numbers = [1, 2, 3, 4, 5];

Now, let us write a function that adds all the numbers together and returns the total sum.

The fastest thing that might have come to mind is to loop over each number in the array and collect the running total in a variable, imperative style:

function sum(numbers) {
  let runningTotal = 0;
  for (let num of numbers)
    runningTotal += num;
  return runningTotal;
}

Let’s go through the solution line by line.

1. First, we initiate and define runningTotal to 0.
2. Then we use a for loop construct to iterate the array and keep adding the current number torunningTotal.
3. When we are done with the numbers, the loop breaks, and the runningTotal is returned.

This method is imperative because it uses statements and mutable variable (the runningTotal) to keep track of a changing state of the program.

To be clear, this is how the computer works. C and Assembly languages are very procedural and imperative because they talk to the computer at a very low level closer to the metal. A computer does very few things more than repeating instructions, store values in its memory, and change those values to something else. Just like the human brain, a computer is a state machine. Functional programming is an attempt to abstract programming with a computer to a logic machine, instead of the first.

Now, let’s try again. This time, we will try to write a variation that does not store a total running sum in any variable.

We will be using recursion. Recursion is based on the fact that a function can be reused and called within itself to solve a problem that can be broken down into smaller repetitive small incremental and inductive steps in which each one calls the same function with a variation of the original input until a certain condition is satisfied.

For example, we will use recursion to build a string from an array of characters. The pseudocode would look like this:

function buildWord(chars) {
  // base case:
  
  if chars' length is 1
    return the only char
  // induction:
  return first char + buildWord(chars minus the first char)
}

Take your time to read this carefully. Here is a question to test your understanding:

If ['f', 'o', 'o'] is provided as an argument to buildWord as such:

buildWord(['f', 'o', 'o'])

by the second time buildWord is called, what would be the argument?

Most of the time, the hint lies in the base case. The base case is the ultimate trap that guarantees the recursion always exits. In this case, the base case catch on when characters only have one character left. This is because in each call,characters is induced by removing its first character, set it as the implicit state in the current frame, then feed the induced array into the next call to buildWord. This goes on until the base case returns. Here is the induction portrayed step-by-step:

buildWord(['f', 'o', 'o'])
'f' + buildWord(['o', 'o'])
'f' + ('o' + buildWord(['o']))    // base case! return 'o' and fold
'f' + ('o' + ('o'))
'f' + ('oo')
'foo'

And here it is in Javascript:

function buildWord(chars) {
  if (chars.length == 1) return chars[0];
  return chars[0] + (chars.slice(1));
}

Now, revisiting the previous sum function, we could re-write it in a similar fashion like this:

function sum(numbers) {
  if (numbers.length == 1) return sum[0];
  return numbers[0] + sum(numbers.slice(1));
}

Or we could do it in ES6 pattern-matching, which makes it a bit clearer:

function sum(numbers) {
  let [first, ...rest] = numbers;
  if (rest.length == 0) return first;
  return first + sum(rest);
}

A recursive function follows this convention:

1. Base case. This branch is mandatory as it provides the way out from the recurring loop. The base case must provide a condition that will eventually become true and returns from the function or the program’s stack will quickly overflow.
2. Induction case. This branch returns a recursive call to itself or an expression consisting of the recursive call. This breaks down the problem into smaller chunks that can be solved over and over by the same function provided the input to the subsequent call gets induced gradually. In the above case, as sum is being called each time, the array provided as the numbers the argument is being induced by one starting element at a time.

We can walk through each step like so:

sum([1, 2, 3, 4])
1 + sum([2, 3, 4])
1 + (2 + sum([3, 4]))
1 + (2 + (3 + sum([4])))
1 + (2 + (3 + (4))
1 + (2 + (7))
1 + (9)
10

Now if you look closely, at each pair of increasing parentheses, the sum of each step is being “frozen” in each one. How could this be stored without an explicit local variable? At this point, let’s talk about the stack.

Stack

What stack is and it works internally is not as important as how it’s useful in solving problems. We can think of a stack as a place we can store quick variables and values by pushing them in and they would automatically pop out at the end of a function’s scope.

For example, let’s inspect this not-so-useful function with a few local variables:

function A(v0) {
  let v1 = 1;
  let v2 = "hello";
  return;
}

When function A is called (with or without an argument), the stack is pushed to “give room” to variables v0, v1, and v2(Yes, v0 is local to this scope as the other two). As soon as A returns, the stack pops those variables out, effectively expiring them and the values assigned to them. No local variable can live beyond its birth scope.

A function like sum is just an ordinary function just like A. They both push the stack each time they are called and pop it when they return. The only difference is sum does not return right away like A does. It calls itself one or more times, creating a new stack frame each time until it hits the base case. Only then does it start to unwind, returning the local state back to the previous frame before destroying the current frame, this value is then used in the calculation in the current frame before returning the result back to the previous one, and vice versa.

This means that until the base case is hit, no calculation has been performed whatsoever.

Tail Recursion

However, in general, recursive functions are memory and/or time expensive. For every step, a new stack frame is being created. Furthermore, all the steps must be completed before the calculation can be performed backward. If only we could store the state, or the result of the current operation and pass it forward to the next recursion. That can be done with tail recursion or tail call.

Tail recursion simply injects the result of the last operation as the argument to the next call, thus effectively doing the calculation at each step and passing on the state to the next one.

Take a look at the sum function re-written to use tail recursion:

function sum(numbers, runningTotal = 0) {
  if (numbers.length == 0) return runningTotal;
  return sum(numbers.slice(1), runningTotal + numbers[0]);
}

The calculation is being performed “forward”, instead of “backward”. Since the running sum is passed at each frame to the next function call, there’s no need to fold back.

We can follow the steps like so:

sum([1, 2, 3, 4], 0)
sum([2, 3, 4], 0 + 1)
sum([3, 4], 1 + 2)
sum([4], 3 + 3)
sum([], 6 + 4)
10

The result is returned right away, and in a language that supports generator and yielding, each iteration can yield the immediate running sum. This makes the program written using tail recursion more memory and time efficient, especially in languages that are optimized for this technique.

Recursion in a Functional Language

And here is why I wrote I understood recursion much better with a functional language. Recursion might seems like overkill in some languages, but it is the bread and butter of many functional languages, some of which do not have a looping construct. This is because most functional languages are created to mimic mathematical expressions, and recursion and induction are both natural to the world of maths and logic.

With powerful pattern-matching in a functional language like Ocaml, recursion becomes quite graphical:

let rec sum numbers =
  match numbers with
  | [] -> 0
  | first :: the_rest -> first + sum the_rest
;;

or the tail-call version

let rec sum numbers running_total =
  match numbers with
  | [] -> running_total
  | first :: the_rest -> sum the_rest (running_total + first)
;;

The pipe notation | reads “branch”. Pattern matching concerns branching out possible matches. In this case, the first branch is the base case and the second one is the induction case.

Let’s look at one more function to get the last number on the list:

let rec last numbers =
  match numbers with
  | [] -> 0
  | [last_el] -> last_el
  | _ :: the_rest -> last the_rest
;;

Ocaml lets us express the shape of the list to be matched instead of using a condition to inspect a certain state, like in the use of arr.length in the previous JavaScript code.

For a more elaborate and in-depth look in recursion and stack frames plus mind-blowing graphics, check out this post.

For a fun little-related topic on the art of recursion in Inception film, see this.

If you like this, please drum your clicks on those claps 👏 a few time for you will you?