I want to achieve the same result I can get with this code:

function fibs(n) {
  let fibs = []
  for (let i = 0; i <= n; i  ) {
    if ((i <= 1)) fibs.push(i)
    else fibs.push(fibs[i - 1]   fibs[i - 2])
  }
  return fibs
}

console.log( fibs(8) )

with a recursive function.

Obviously, when you console.log(fibs(8) it renders a list like this: [0, 1, 1, 2, 3, 5, 8, 13, 21]

My recursive function looks like this:

function fibsRec(n) {
  if (n < 2) return n
  return fibsRec(n - 1)   fibsRec(n - 2)
}

console.log( fibsRec(8) )

and if you console.log(fibsRec(8)) it returns 21, which is the Fibonacci of 8, but doesn't give me a list of all the Fibonacci numbers before it. How can I get the list without a loop? **How can I get the same outcome as fibs() with fibsRec() **

CodePudding user response：

I would do this like this (it's also a little bit faster because of caching):

function fibsRec(n) {
  const cache = {
    1: 1,
    0: 1
  }
  
  rec(n)

  return Object.values(cache)

  function rec(n) {
    if (cache[n]) return cache[n]
    cache[n - 1] ??= rec(n - 1)
    cache[n - 2] ??= rec(n - 2)
    return cache[n - 1]   cache[n - 2]
  }
}



console.log(fibsRec(8))

CodePudding user response：

Of course the easy answer would be to make a wrapper function that loops and calls fibsRec(i) each time, but that's not what you're looking for.

First, you need to think about what fibsRec is doing to see why this isn't naturally as simple as it sounds. As you already know it gets the nth fibonacci number by finding the (n-1)th and (n-2)th and to get those, it keeps going further back.

But that means that to get the n-1 and n-2 numbers, you need to generate the sequence to n-1 and n-2, not only that, but when you start generating that sequence for, let's say n-1, and you have to calculate it's previous indices, then you need two more sequences, and so on and so on. It's extremely inefficient.

But the reason I'm bringing this up, is to say that we can't just create an empty array and have it push the number we'd return before returning it, because we're making so many sequences, our array is gonna contain all those results.

Look at this:

function fibArray(n) {
  const output = [];

  function fibsRec(n) {
    if (n < 2) {
      output.push(n)
      return n;
    }

    let num =  fibsRec(n - 2)   fibsRec(n - 1) 
    output.push(num);
    return num;
  }
  fibsRec(n);
  return output
}

console.log( fibArray(8) )

See how many times we're calculating a number on the fibonacci sequence?

We definitely can't directly use this approach. But what we can use is dynamic programming. What we'll do is, memoize (save) each fibonacci number we calculate to a dictionary, and the next time we're looking for it, instead of recursing a new sequence, we'll just get it from the dictionary directly.

That way, we're getting each fibonacci number only once. So when we calculate it, we can push it to our output array, and it'll be a clean fibonacci sequence.

function fibArray(n) {
  const output = [];
  const fibs = {}; // Create memo (a dictionary)
  
  function fibsRec(n) {
    if (fibs[n]) return fibs[n]; // Check memo
    if (n < 2) {
      fibs[n] = n;
      if (n) output.push(n) // ignore 0
      return n;
    }
    
    let num =  fibsRec(n - 2)   fibsRec(n - 1) // Start with n-2 to eventually call fibsRec(0) before fibsRec(1) and push them in that order
    fibs[n] = num; // Memoize
    output.push(num);
    return num;
  }
  fibsRec(n);
  return output
}

console.log( fibArray(8) )