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

Javascript – Fibonacci sequence using recursion

I try to make a function that returns an arrays of fib sequence up to Nth term. I’ve done this using iteration and returning n-th term alone with recursion but I can’t understand how to save the terms in the array using recursion.

I tried with this but it only returns last term and not as an array but a number

function fibRec(n) {

  if (n == 1) {
    return 0;
  }
  if (n == 2) {
    return 1;
  }
  let array = [];
  return (array[n] = fibRec(n - 1) + fibRec(n - 2));
}

console.log(fibRec(10))
Tags:

3

Answers


  1. 0

    You are not pushing to the array

    const fibRec = (n) => {
  if (n <= 0) return [];    // n is zero or negative
  if (n === 1) return [0];  // return [0] if n is 1
  const result = [0, 1];    // Initialize with the first two Fibonacci numbers

  const fillFib = (currentIndex) => {
    if (currentIndex >= n) return;  // stop recursion when we run out of numbers
    result[currentIndex] = (result[currentIndex - 1] + result[currentIndex - 2]);  // next Fibonacci number
    fillFib(currentIndex + 1);     // Recurse to compute the next number in sequence
  };
  fillFib(2);  // Start from the 3rd third element
  return result.slice(0, n);  // Return the sliced array up to nth element
}


console.log(fibRec(10));
    Login or Signup to reply.
  2. 0

    Your array variable is created for each execution of Fib, so you have multiple of them, and every one of them starts out empty, and then gets one assignment to its n index, and is then discarded (since it is local).

    Moreover, if you want the caller to get an array, then you’ll have to return an array, which you currently don’t: all three return statements return a number, not an array.

    The first thing to ensure is that you always return an array. But then realise that you cannot just add up the two return values you get from the recursive calls, since they are now … arrays!

    You’ll also not make two recursive calls, but just one (with n-1), as it will return you the array that also includes the n-2 entry.

    Finally, make sure that you just have one array that is shared by all recursive calls — so you’d pass it as argument. You can create that array once by using the default value for the second argument.

    For instance:

    function fibRec(n, array=[0,1]) {
    if (n >= array.length)  { // We didn't calculate it yet
        fibRec(n - 1, array); // Don't perform a sum with returned value
        array[n] = array[n-1] + array[n-2]; // Perform the sum here
    }
    return array; // Always return the array
}

console.log(fibRec(10))

    All in all, this is rather clumsy: as you know you have to populate the array incrementally anyway, using a recursion stack is just wasted space. Just go for the iterative version.

    Login or Signup to reply.
  3. 0

    In case you’re interested in higher numbers and you explicitly want to use recursion (although it might take a long time for computing the output), none of the other answers so far work since both produce a RangeError. What you want then is called trampolining and you need a bit more "machinery" for it, however it enables you to call tail recursive functions in a stack safe manner.

    Below is a simple implementation and a working example:

    const fibRec = (upTo) => recur(
  (done, loop, { values, nextValue }) => {
    return nextValue >= upTo
      ? done(values)
      : loop({
          values: values.concat(nextValue),
          nextValue: values[values.length - 1] + nextValue
        });
  },
  { values: [0], nextValue: 1 }
);

console.log(fibRec(10000));




/* --- helpers */
function recur(func, initValue) {
  let result = func(Done, Loop, initValue);
  while (result instanceof Loop) {
    result = func(Done, Loop, result.value);
  }
  return result.value;
};

function Loop(value) {
  const x = Object.create(Loop.prototype);
  x.value = value;
  return x;
};

function Done(value) {
  const x = Object.create(Done.prototype);
  x.value = value;
  return x;
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search