Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How to return the right array for f(0), tail-call optimized Fibonacci?

I’m studying recursion and I’m trying to make a tail-call optimized Fibonacci which returns an array of Fibonacci numbers up to the argument passed.

The problem I am encountering is with Fibonacci of 0, which should return [0], but now returns [0, 1].

// Fibonacci recursive, tail call optimised, returns an array
function fibRecursiveTCO(n) {
  return fibonacciRecursiveTCO(n, 0, 1);
}

function fibonacciRecursiveTCO(n, a, b, result = [0, 1]) {
  if (n <= 1) {
    return result;
  }

  const next = a + b;
  result.push(next);
  return fibonacciRecursiveTCO(n - 1, b, next, result);
}

console.log(fibRecursiveTCO(0)); // expected [0], returns [0, 1] instead
console.log(fibRecursiveTCO(1)); // [0, 1]
console.log(fibRecursiveTCO(19)); // Array(20) [0, 1, ..., 4181]
Tags:

2

Answers


  1. Chosen as BEST ANSWER
    0

    After playing with this for a while, I found an answer that returns all the expected results:

    function fibRecursiveTCO(n) {
  return fibonacciRecursiveTCO(n, 0, 1);
}

function fibonacciRecursiveTCO(n, a, b, result = [0, 1].slice(0, n + 1)) {
  if (n <= 1) {
    return result;
  }

  const next = a + b;
  result.push(next);
  return fibonacciRecursiveTCO(n - 1, b, next, result);
}

console.log(fibRecursiveTCO(0)); // [0]
console.log(fibRecursiveTCO(1)); // [0, 1]
console.log(fibRecursiveTCO(19)); // Array(20) [0, 1, ..., 4181]


  2. 0

    First of all, if you are using recursion, then reap its benefits. In our case, you have a composite problem, i.e., get the first 19 Fibonacci numbers and you should always decompose your problem to similar, but simpler sub-problems. So, what the result should be for F(19)? The result should be F(17) + F(18) and so on backwards.

    So let’s automate this decomposing of the problem until we reach the trivial case of F(1), which is 1 and for which you want a result of [0, 1]. So the caller of fibonacciRecursiveTCO(n - 1) will get the Fibonacci numbers up to F(n – 1), so when the function returns, you have both F(n – 2) and F(n – 1) at your disposal (provided that n >= 2, because otherwise you have a trivial case) and you can add the two and concat the result to your previous result.

    Now that we handled the more complex cases properly, decomposing the problem into sub-problems and building back the result from the trivial towards the more complex, let’s turn our focus to the trivial cases.

    For the sake of simplicity the implementation I have given assumes that n will be a natural number and completely ignores the possibility of negative, non-discrete or non-numeric inputs. In a professional environment you will need to contemplate on what to do in such cases too, but here we deal only with natural numbers.

    We have two trivial cases for natural numbers. Either you have n being 0 or 1. In both cases we return result, that is, the default. Yet, we face the problem of needing two separate defaults, [0] being the default when n is 0 and [0, 1] being the default when n is 1. So, which of the two should be the default default? Well, since all inputs will boil down to n being 1’s default, except for the exceptional case when n was 0, the default default is chosen to be [0, 1].

    However, then something will need to know that for n being 0, the default needs to be [0]. I handled this in fibRecursiveTCO, which will specify what the default result is if n was 0, but you might want to make sure that fibonacciRecursiveTCO is unreachable apart from fibRecursiveTCO so the defaults will be guaranteed to be handled properly. For that purpose you could create a class and make sure that fibRecursiveTCO is public and fibonacciRecursiveTCO is private. Read more here: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes/Private_properties

    // Fibonacci recursive, tail call optimised, returns an array
function fibRecursiveTCO(n) {
  return n ? fibonacciRecursiveTCO(n) : fibonacciRecursiveTCO(n, [0]);
}

function fibonacciRecursiveTCO(n, result = [0, 1]) {
  if (n <= 1) {
      return result;
  }
  let previous = fibonacciRecursiveTCO(n - 1, result);
  return previous.concat(previous[previous.length - 2] + previous[previous.length - 1]);
}

console.log(fibRecursiveTCO(0)); // expected [0], returns [0, 1] instead
console.log(fibRecursiveTCO(1)); // [0, 1]
console.log(fibRecursiveTCO(19)); // Array(20) [0, 1, ..., 4181]
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search