Finding all Fibonacci numbers less than or equal to a number

Question

I am trying to implement a function in JavaScript that returns an array of all the Fibonacci numbers up until a certain number (num). During my research I came across this answer: Calculate Fibonacci numbers up to at least n. I implemented their solution in JavaScript and Python, but found that their solution has a bug in it. The problem is that the last element is sometimes wrong. Here is the code I wrote based off of the solution I found in the answer linked above.

function findFibs(num) {
  
  if (num < 2) {
    return [1,1];
  } else {
    var fibs = findFibs(num - 1)
    if ((fibs[fibs.length - 1]) < num ) {
      fibs.push(fibs[fibs.length - 1] + fibs[fibs.length - 2])
    }
    return fibs;
  }
}

console.log(sumFibs(20));

The expected output of this code is:[ 1, 1, 3, 5, 13 ] , but the actual output is [ 1, 1, 3, 5, 13, 21 ] . What is it that I'm missing?

Answer 1

functional

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutations, variable reassignments, and other side effects. Consider a more functional approach -

Given a limit and two seeds, a and b -

1. if seed a is greater than the input limit, return the empty result
2. (inductive) a is less than or equal to the limit. recur on the sub-problem (limit, b, a + b) and append it to the singleton [a]

This encodes as a pure functional expression -

const fibs = (limit, a = 1, b = 1) =>
  a > limit
    ? []                                 // #1
    : [ a, ...fibs(limit, b, a + b) ]    // #2
    
console.log(fibs(20))
// [ 1, 1, 2, 3, 5, 8, 13 ]

imperative

If I were to use imperative style for this program, I think I would reach for a generator -

function* fib (a, b)
{ yield a
  yield *fib(b, a + b)
}

function* fibs (limit)
{ for (const n of fib(1, 1))
    if (n < limit)
      yield n
    else
      return
}

console.log(Array.from(fibs(20)))
// [ 1, 1, 2, 3, 5, 8, 13 ]

stack-safe

Seen above in fib, we can use recursion with imperative style but because it can overflow the stack, it would make more sense to use a loop in this situation -

function* fib (a, b)
{ let t
  while (true)    // stack-safe, but not recursive
  { yield a
    t = a
    a = b
    b = t + a
  }
}

function* fibs (limit)
{ for (const n of fib(1, 1))
    if (n < limit)
      yield n
    else
      return
}

console.log(Array.from(fibs(20)))
// [ 1, 1, 2, 3, 5, 8, 13 ]

BigInt

The Fibonacci sequence quickly produces large numbers that JavaScript will approximate using scientific notation. The 102^nd term is 927372692193079200000 and the 103^rd term is 1.5005205362068963e+21. This is due to the size constraints of JavaScript's numbers. Using the newer BigInt we can get around this easily -

function* fib (a, b)
{ let t
  while (true)
  { yield a
    t = a
    a = b
    b = t + a
  }
}

function* fibs (limit)
{ for (const n of fib(1n, 1n)) // <- bigint
    if (n < limit)
      yield n
    else
      return
}

for (const n of fibs(1e70))
  console.log(String(n))       // <- bigint to string

StackOverflow.com truncates output to show only the last 50 lines. Check your browser's console for the full output -

...
426547842461739379460149980002442288124894678853713953114433
690168906931029935139391829792095612517948949963798093315456
1116716749392769314599541809794537900642843628817512046429889
1806885656323799249738933639586633513160792578781310139745345
2923602405716568564338475449381171413803636207598822186175234
4730488062040367814077409088967804926964428786380132325920579
7654090467756936378415884538348976340768064993978954512095813
12384578529797304192493293627316781267732493780359086838016392
20038668997554240570909178165665757608500558774338041350112205
32423247527351544763402471792982538876233052554697128188128597
52461916524905785334311649958648296484733611329035169538240802
84885164052257330097714121751630835360966663883732297726369399
137347080577163115432025771710279131845700275212767467264610201
222232244629420445529739893461909967206666939096499764990979600
359579325206583560961765665172189099052367214309267232255589801
581811569836004006491505558634099066259034153405766997246569401
941390895042587567453271223806288165311401367715034229502159202
1523202464878591573944776782440387231570435521120801226748728603
2464593359921179141398048006246675396881836888835835456250887805
3987795824799770715342824788687062628452272409956636682999616408
6452389184720949856740872794933738025334109298792472139250504213
10440185009520720572083697583620800653786381708749108822250120621
16892574194241670428824570378554538679120491007541580961500624834
27332759203762391000908267962175339332906872716290689783750745455
44225333398004061429732838340729878012027363723832270745251370289
71558092601766452430641106302905217344934236440122960529002115744
115783425999770513860373944643635095356961600163955231274253486033
187341518601536966291015050946540312701895836604078191803255601777
303124944601307480151388995590175408058857436768033423077509087810
490466463202844446442404046536715720760753273372111614880764689587
793591407804151926593793042126891128819610710140145037958273777397
1284057871006996373036197088663606849580363983512256652839038466984
2077649278811148299629990130790497978399974693652401690797312244381
3361707149818144672666187219454104827980338677164658343636350711365
5439356428629292972296177350244602806380313370817060034433662955746
8801063578447437644962364569698707634360652047981718378070013667111
14240420007076730617258541919943310440740965418798778412503676622857
23041483585524168262220906489642018075101617466780496790573690289968
37281903592600898879479448409585328515842582885579275203077366912825
60323387178125067141700354899227346590944200352359771993651057202793
97605290770725966021179803308812675106786783237939047196728424115618
157928677948851033162880158208040021697730983590298819190379481318411
255533968719576999184059961516852696804517766828237866387107905434029
413462646668428032346940119724892718502248750418536685577487386752440
668996615388005031531000081241745415306766517246774551964595292186469
1082459262056433063877940200966638133809015267665311237542082678938909
1751455877444438095408940282208383549115781784912085789506677971125378
2833915139500871159286880483175021682924797052577397027048760650064287
4585371016945309254695820765383405232040578837489482816555438621189665
7419286156446180413982701248558426914965375890066879843604199271253952

Answer 2

Break down the code first, to understand what it is doing.

function findFibs(num) {

    // checking if the given num is less than 2
    if (num < 2) {
        return [1, 1];
    
    } else { 
        // decrement the given number by 1, which is 19, 18, 17....
        // and reenter the loop with it
        var fibs = findFibs(num - 1)
        
        // grab the last and second last numbers
        const a = fibs[fibs.length - 1];
        const b = fibs[fibs.length - 2];

        // check if the last number is less than num
        // AND if the sum of a+b is less than num
        // see? you should also check for (a + b) < num. this is what you missed.
        if (a < num && (a + b) < num) {

            // if so, add a new item to the array fibs
            fibs.push(a + b)
        }
        return fibs;
    }
}

console.log(findFibs(20));

check out the push method on W3Schools

By the way, your last line of code console.log(sumFibs(20)); should be console.log(findFibs(20));. Otherwise your code does not run properly. Happy coding!

Answer 3

The reason for the output 21 is due to the wrong condition ins if statement.
(fibs[fibs.length - 1]) < num

It means where the last entry was 13 which is less than 20. so 13 adds up with 8 and stores as 21 in fibs array. if you change the if statement to
if ((fibs[fibs.length - 1]+ fibs[fibs.length - 2]) < num )

Then you can expect the output you needed.

new code:

function findFibs(num) {
  
    if (num < 2) {
      return [1,1];
    } else {
      var fibs = findFibs(num - 1)
      console.log(fibs)
      if ((fibs[fibs.length - 1]+ fibs[fibs.length - 2]) < num ) {
        fibs.push(fibs[fibs.length - 1] + fibs[fibs.length - 2])
      }
      return fibs;
    }
  }
  
  console.log(findFibs(20));

Answer 4

You can set a condition before push the last item:

toPush < num ? fibs.push(toPush) : 0;

function findFibs(num) {
  
  if (num < 2) {
    return [1,1];
  } else {
    var fibs = findFibs(num - 1)
    if ((fibs[fibs.length - 1]) < num) {
      let toPush = fibs[fibs.length - 1] + fibs[fibs.length - 2];
      toPush < num ? fibs.push(toPush) : 0;
    }
    return fibs;
  }
}

console.log(findFibs(20));