One of the key concepts used in functional programming (FP) is recursion—the ability of a function to call itself. You may have heard these things:

• Recursion is difficult to understand.
• Recursion is slow.
• Recursion is dangerous because it can lead to a condition called stack overflow.
• Many FP languages don’t use loops; they only use recursion.

This may have put you off the idea of using those FP languages or using recursion at all. Fear not; it is possible to tame recursion using a technique called tail recursion. In this article, I’ll be using ReasonML for code examples.

A Typical Example

This is a typical example you will see when people introduce recursion, and, to be honest, it can be a little bit scary.

The first example will be to write a function that finds the sum of squares of an array (a useful thing to calculate in statistical formulas). Here’s how you create an array of integers in ReasonML.

let numbers = [|3, 7, 4|];

Here’s how we solve the problem using recursion. We first consider the simplest possible case, also called the base case. The sum of squares of an empty array is zero. For any other array, we take the square of the first number and add the sum of squares of the rest of the numbers (there’s our recursion). Here’s how we express it in ReasonML.

let rec sumOfSquares = (data) => {
    if (Js.Array.length(data) == 0) {
        0;
    } else {
        data[0] * data[0] + sumOfSquares(Js.Array.sliceFrom(1, data));
    };
};

let result = sumOfSquares(numbers);

Js.log2("The sum of squares is", result);

In ReasonML, we use rec to indicate that we will be calling this function recursively. We’re using two functions from the Js.Array module: length() to find the length of the array. The sliceFrom() function returns the portion of the given array from the index you specify (in our case, index 1) to the end. The call to sliceFrom(1, data) returns an empty list if you give it an array with only one element, and that is exactly what we want.

In ReasonML, if is an expression, not a statement, so we don’t need to assign the result of the if or else branch to a result variable. ReasonML functions take the last expression that the function evaluates as the return value, so no explicit return is necessary.

What’s going on behind the scenes? Let’s see what the function is doing when given the numbers array [|3, 7, 4|].

• Square the first number. 3^2 → 9
• Add 9 to the sum of squares of the rest of the array: [|7, 4|]. Use recursion to figure that out (recursion #1).
  • Square the first number. 7^2 → 49
  • Add 49 to the sum of squares of the rest of the array: [|4|]. Use recursion #2 to figure that out.
    • Square the first number. 4^2 → 16
    • Add 16 to the sum of squares of [||]. Use recursion #3 to figure that out.
      • The sum of squares of the empty list is zero.
    • Complete the addition started in recursion #3: 16 + 0 → 16
  • Complete the addition started in recursion #2: 49 + 16 → 65
• Complete the addition started in recursion #1: 9 + 65 → 74

Ye cats! That looks incredibly complicated. The way this (and most typical introductions to recursion) are written, we have to put our calculation “on hold” until we have evaluated the remaining numbers. That requires us to store our intermediate results somewhere. That “somewhere“ is called the stack, and it has limited size. If we have a large array, we’ll have more intermediate results than the stack can hold, it will overflow, and our program will crash.

Not only do we have to hold off on our calculations, once we get to the base case, we have to climb back up the ladder of additions we’ve been building.

No wonder people flee from the room, shrieking, whenever they see the word “recursion.”

Please Don’t Run Away

Take a deep breath. Say “om.” Now let’s do a complete restart and introduce recursion with...

A Not-scary Example

Let’s use recursion to solve this problem: given an array of numbers, find the index of the first negative value. Here’s our array of quarterly account balances:

let balances = [|563.22, 457.81, -309.73, 216.45|];

We’ll use a function called debitIndex() that takes two parameters: the array to search, and a starting index. Here’s our pseudocode for that function.

To find the first negative value in an array starting at an index number:

1. Is our current index equal to the array length? If so, we’ve hit the end of the array, and we return -1 to indicate that we haven’t found a negative value.
2. Is the value at the current index negative? That means we’ve found the debit, and we’ll return the index number.
3. Otherwise, we’ll find the first negative value in the array starting at the next index number.

Steps 1 and 2 tell us when we can stop looking. These are called the base cases. Step 3 is where the recursion happens—it restates the problem in terms of itself.

Here’s the ReasonML code:

let rec debitIndex = (data, index) => {
   if (index == Js.Array.length(data)) {
      -1;
   } else if (data[index] < 0.0) {
      index;
   } else {
      debitIndex(data, index + 1);
   }
};

let result = debitIndex(balances, 0);
Js.log2("Result is ", result);

ReasonML is very strict about not mixing floating point and integer values. Because the balances array contains floating point numbers, we have to compare to floating point 0.0 rather than the integer value 0.

Now let’s see what happens when we make our call to debitIndex(balances, 0)

• The index (0) isn’t equal to the length of the array.
• data[0] is 563.22, which is not less than zero.
• Do a recursive call with the data array and index 1
  • The index (1) isn’t equal to the length of the array.
  • data[1] is 457.81, which is not less than zero.
  • Do a recursive call with the data array and index 2.
    • The index (2) isn’t equal to the length of the array.
    • data[2] is -309.73, which is less than zero. Return the index (2).

That wasn’t as bad as the first example. We didn’t have to put any calculations on hold. When we hit a base case, we were finished. We didn’t have to climb back up a ladder of nested calls.

What made the difference? Let’s compare the two recursive calls:

data[0] * data[0] + sumOfSquares(Js.Array.sliceFrom(1, data));
// vs.
debitIndex(data, index + 1);

In the first example, the recursion is the next-to-last thing we do (the last operation in the expression is the addition). We have to put the calculation on hold and save our partially-completed addition on the stack.

In the second example, the recursion is the last (and only) thing we do.

When the recursion is the last operation, that is called tail recursion.

In tail recursion, when you hit the base case, you have finished.

Taming the Scary Example

If we can make our recursive call from the first example tail recursive, we’ll have a non-scary recursion. Let’s examine the second example a bit more closely.

The reason we were to do the second example as tail recursion was because the parameters contained all the information needed to continue the process. There was no need to put any calculations on hold.

If we can do the same thing in the first example—make the partially-completed addition one of our parameters in the recursive call—we’ll be able to make it our only operation and end up with a non-scary tail recursive function.

Here’s the code that makes that happen:

let rec sumOfSquares = (accumulator, data) => {
  if (Js.Array.length(data) == 0) {
     accumulator 
  } else { 
     sumOfSquares(accumulator + data[0] * data[0],
        Js.Array.sliceFrom(1, data));
  }
};

let answer = sumOfSquares(0, data);

This time, our function has two parameters: the data array and an accumulator to hold our partially-completed calculation.

The base case changes: when we hit an empty array, we return whatever the calculation has accumulated.

If the array isn’t empty, the recursive call is the last—and only—thing we do. We pass along the partial calculation (the accumulator plus the square of the first item) and the remaining items in the array.

Let’s see what happens now when given the numbers array [|3, 7, 4|].

• The accumulator is zero, and the array is [|3, 7, 4|].
• Do a recursive call with 0 + 3^2 as the accumulator and the remaining items.
  • The accumulator is 9, and the array is [|7, 4|].
  • Do a recursive call with 9 + 7^2 as the accumulator and the remaining items.
    • The accumulator is 58, and the array is [|4|].
    • Do a recursive call with 58 + 4^2 as the accumulator and the remaining items.
      • The accumulator is 74, and the array is [||].
      • The array is empty. Return the accumulator (74).

Voilà—a non-scary recursion.

You can almost always use this accumulator trick to turn a “hold-off-and-climb-back-up” recursion into a “base-case-and-finished“ tail recursion.

Tail Recursion’s Big Win

There’s another enormous advantage of using tail recursion. Look at that last analysis of the sum of squares. Was there any real need to indent the list? If you line all the steps up at the left and cut out the recursion:

• The accumulator is zero, and the array is [|3, 7, 4|]
• The accumulator is 9 (3^2 + 0), and the array is [|7, 4|]
• The accumulator is 58 (7^2 + 9), and the array is [|4|]
• The accumulator is 74 (4^2 + 58), and the array is [||]

That looks a whole lot like a plain old while loop. ReasonML (and some other functional programming languages) take advantage of this. When the compiler detects tail recursion, it doesn’t use the stack at all. Instead, it compiles the recursion into a while loop. The stack is bypassed entirely, and there’s no possibility of stack overflow.

Bonus Section: Helper Functions

If you are approaching information overload, feel free to skip this section. You can come back and read it later.

The good news about tail recursion is that it is conceptually simpler and it can be optimized. The bad news is that the people using the function have to pass an extra parameter for the accumulator. They have to say sumOfSquares(numbers, 0) instead of sumOfSquares(numbers) and debitIndex(balances, 0) instead of debitIndex(balances). But we have a trick to solve that: helper functions.

ReasonML lets you nest functions within functions. We can rewrite the debitIndex() function to use only one parameter as follows:

let debitIndex = (data) => {
  let rec helper = (index) => {
    if (index == Js.Array.length(data)) {
      -1; 
    } else if (data[index] < 0.0) {
      index;
    } else {
      helper(index + 1); 
    }   
  };  

  helper(0);
};

let result = debitIndex(balances);

In this version, debitIndex() takes only one parameter: the array of values. It calls the nested helper() function to recursively move the index forward through the array until it finds a negative value. We don’t have to pass data to the helper() function; it is available in the scope of the outer function and it’s not changing from one call to the next.

Similarly, here’s the helper function version for the sum of squares:

let sumOfSquares = (data) => {
  let rec helper = (accumulator, data) => {
    if (Js.Array.length(data) == 0) {
       accumulator 
    } else { 
       helper(accumulator + data[0] * data[0],
          Js.Array.sliceFrom(1, data));
    };  
  };  

  helper(0, data);
};

let result = sumOfSquares(numbers);

In this case we do have to pass the data array to the helper() function because it is changing every time we call the helper function.

Summary

• When solving a problem recursively, figure out the base case first.
• Whenever possible make the function tail recursive— make the recursive call the last operation. You can do this by carrying along any intermediate results you need in the call parameters.
• Use a language that optimizes tail recursion into a while loop. Your code will run faster and safer.