I recently wrote a recursive function, getFibonacciSequence(), that would return an array of Fibonacci numbers. The function accepts an argument, length, to get a Fibonacci sequence of the specified length. E.g., if 5 is passed, the returning array would be an array of Fibonacci numbers of length 5, e.g. [0, 1, 1, 2, 3].

To recursively build up the sequence of Fibonacci numbers, I had my function take a second argument, array, which stores the array currently being built up.

I also had to define a base case that would be the stopping point for my recursive function so that it doesn’t get caught in an infinite calling cycle.

The point at which my recursive function should stop calling itself is when my array’s length is equal to the length argument passed to the function. My function should then return the sequence of Fibonacci numbers.

Otherwise, if the array being built up is still not equal to the length passed to the function, then I should keep building out the array.

When I first wrote this function, I forgot a key component. I forgot to return my recursive call to my function. I was only returning in my base case. See my code below.

    var getFibonacciSequence = function (length, array) {
      // Check to see if length is 0, 1, or 2
      if (length === 0){ 
        return null;
      } else if (length === 1) {
        return [0];
      } else if (length === 2) {
        return [0, 1];
      }

      // The first time our function is called, the array 
      // variable will be undefined. It needs to be set to 
      // [0, 1] because every Fibonacci sequence starts 
      // with 0 and 1. Then with each recursive call, 
      // array will be updated with the current value of 
      // the array. 

      array = array || [0, 1];

      // Base Case
      // If our array length is equal to the length 
      // argument passed to the function, then we have a 
      // Fibonacci sequence of that length and can return 
      // the array of Fibonacci numbers
      if (array.length !== length) {
        return array;
      }

      // Otherwise, we need to keep building up our array
      // To find the next number of the Fibonacci 
      // sequence, we add together the last two numbers 
      // of the sequence
      array.push(
        array[array.length - 1] + array[array.length - 2]
      );
      // recursive call to our function to return our 
      // array if it’s length is equal to the length 
      // provided, or to keep building it
      getFibonacciSequence(length, array);
    };

Why is this problematic? It’s problematic because the first time my function is called, I check to see if my base case is met, which it’s not, so I start to build up my sequence with a recursive call to my function. That first function does not execute a return statement. Functions which do not return anything return undefined by default in JavaScript. The function would keep recursively calling itself until it’s base case is met. Once that happens it will return the Fibonacci sequence to the function which just called it, but not to the function calls above it. See an example of the recursion chain below.

To fix this problem, we simply need to return the recursive function call to make sure that the sequence that eventually gets returned travels up the recursive chain to our very first call to the function.

    var getFibonacciSequence = function (length, array) {
      if (length === 0){ 
        return null;
      } else if (length === 1) {
        return [0];
      } else if (length === 2) {
        return [0, 1];
      }

      array = array || [0, 1];

      // Base Case
      if (array.length !== length) {
        return array;
      }

      // Keep building
      array.push(
        array[array.length - 1] + array[array.length - 2]
      );
      return getFibonacciSequence(length, array);
    };

Our function call getFibonacciSequence(5) will now return [0, 1, 1, 2, 3] instead of undefined.

Tags: