Taming Recursion with Tail Recursion
Tags: reason, recursion, optimization, techniques
Published: 2019-12-17 17:33:14

One of the key concepts used in functional programming (FP) is *recursion*&mdash;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](https://reasonml.github.io) 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.

```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.

```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 &rarr; 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 &rarr; 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 &rarr; 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 &rarr; 16
  * Complete the addition started in recursion #2: 49 + 16 &rarr; 65
* Complete the addition started in recursion #1: 9 + 65 &rarr; 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:

```reasonml
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&mdash;it restates the problem in terms of itself.

Here’s the ReasonML code:

```reasonml
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:

```reasonml
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&mdash;make the partially-completed addition one of our parameters in the recursive call&mdash;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:

```reasonml
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&mdash;and only&mdash;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à&mdash;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:

```reasonml
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:

```reasonml
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&mdash; 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.