In the Part 2 of this series, we gained an intuition for problems that are ideal use cases for recursion. In this article, our focus will be on the performance implications of recursion and identifying when to optimize it for better performance.

I often hear programmers say that recursion is suboptimal. This is not really true as recursion can be as efficient as the while loop. However, it is beneficial to know when to optimize our recursive functions because there are scenarios where using recursion unnecessarily leads to a quadratic solution - O(n^2).

There are generally two techniques for optimizing recursive functions:

• Tail recursion

• Dynamic programming

Tail Recursion

Although we are going to learn about when we can optimize our recursive functions by making it tail recursive, it is helpful to know that most language compilers have built-in capabilities to recognize and optimize functions that can be tail recursive. This feature is known as Tail Recursion Optimization.

However, as progammers, identifying recursive functions that can be made tail recursive and writing tail recursive functions is an important skill because not all language implementations have this feature.

What is a Tail Recursive Function?

We are going to make use of code samples and diagrams to illustrate these concepts as they can be quite unwieldy at first, so don’t fret. However, the definition follows:

A tail recursive function is a function whose recursive call is in tail position.

A function call is in tail position when there is nothing left to do after the function body is evaluated.

To demonstrate these concepts, we will take a look at the sum of an array example we used in the Part 1 of this series.

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

function sum(arr) {
  if (arr.length === 0) {
    return 0;
  }

  let head = arr.shift();
  // this is not a tail recursive function because
  // after the body of sum is evaluated, we still have
  // something left to do, which is to add the result
  // of the sum function call to the head variable.
  // Therefore, the sum function call is not in tail position.
  return head + sum(arr);
}

In the Part 1 of this series, we saw that every time a function is called, a stack frame is added to the call stack. This is necessary to keep track of the return value state of individual function calls. However, it is sometimes unnecessary as we can achieve the same outcome by making use of only one stack frame. By so doing, we save computing resources leading to efficient solutions. This is the value of Tail Recursive Functions.

This is the state of the call stack handling a recursive function call that isn't tail recursive.

To refactor our sum function to be tail-recursive, we need to define a helper function that accumulates the result of our sum operation at each step.

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

function sum(arr) {
  // nested helper function to help accumulate the sum of the array
  function sumHelper(acc, arr) {
    if (arr.length === 0) {
        return acc;
    }

    let head = arr.shift();

    return sumHelper(acc + head, arr);
  }

  // this is tail recursive because after the body of the 
  // sum function is evaluated, there is nothing left to do.
  // Therefore, the sum function is in tail postion.
  return sumHelper(0, arr);
}

console.log(sum(numbers));

With the help of the helper function (pun absolutely intended 😌), we accumulate the return value state at each step and return it when the array is empty. This relieves the call stack the duty of maintaining the return value state so that the call stack can make use of only one stack frame to execute our sum function.

This is the state of the call stack handling a tail recursive function call.

From this demonstration, we can see that tail recursion comes in handy when there is an accumulation logic over a number (addition, multiplication, e.t.c) or a data structure.

Dynamic Programming

Dynamic programming is a programming pattern that makes use of a data structure to cache results of recursive function calls so that they are available for subsequent recursive calls in order to avoid unnecessary re-computation.

As usual, we are going to demonstrate this with an example. We will solve the Fibonacci sequence problem and then optimize it using Dynamic Programming pattern.

function fibonacci(n) {
    if (n <= 0) {
        return 0;
    }

    if (n === 1) {
        return 1;
    }

    // console.log(`I got called by - ${n}`);

    return fibonacci(n - 1) + fibonacci(n - 2);
}

In this solution, we have two recursive calls to the fibonacci function. These calls compute the result for subsequent arguments to the function and these computations can be duplicated by both functions calls when passed similar arguments. You can see this behaviour by uncommenting the log to the console in the code snippet above and running it in the console or a playground like jsbin.com.

In such a case, Dynamic programming is used to ensure that any result computed by one recursive call is cached so that the other recursive call can retrieve this result when given a similar argument thereby avoiding the need to re-compute this result. This is shown below:

function fibonacci(n) {
    const cache = {};

    function fibHelper(n) {
        if (cache[n]) {
            return cache[n];
        }

        if (n <= 0) {
            return 0;
        } 

        if (n === 1) {
            return 1;
        }

        // console.log(`I got called by - ${n}`);

        return cache[n] = fibHelper(n - 1) + fibHelper(n - 2);
    }

    return fibHelper(n);
}

Dynamic programming is often used when there are more than one recursive function calls in the body of a function definition. However, we can also decide to use the tail recursion technique to optimize such function. Here is the tail recursive version of the Fibonacci function.

function fibonacci(n) {
    function fibHelper(acc1, acc2, n) {
        if (n <= 0) {
            return acc1;
        } 

        if (n === 1) {
            return acc2;
        }

        return fibHelper(acc2, (acc1 + acc2), (n - 1));
    }

    return fibHelper(0, 1, n);
}

In conclusion, knowing when to optimize your recursive functions is a crucial skill to acquire in your quest to become a great programmer. It is also important to note that these optimization techniques are not practical in all cases. The problem we solved in the Part 2 of this series is an example of such case.

I hope this series was fun for you as it was for me. I hope it was helpful in your quest to understand recursion and its performance implications. Thanks for reading and have fun writing recursions 😀.