Generating Fibonacci Sequence

Question

var x   0  var y   1  var z   fib 0    0  fib 1    1   for  i   2  i  lt   10  i        alert x   y     fib i    x   y    x   y    z   y      I m trying to get to generate a simple Fibonacci Sequence but there no output    Can anybody let me know what s wrong

User · Answer

You can refer to below simple recursive function   function fib n         if  n  lt   2  return 1        return fib n-1    fib n-2       console log fib 10     55    Pass on any value to get fibonacci of

User · Answer

My 2 cents    x000D   x000D  function fibonacci num    x000D    return Array apply null  Array num   reduce function acc  curr  idx    x000D      return idx  gt  2   acc concat acc idx-1    acc idx-2     acc  x000D        0  1  1    x000D    x000D   x000D  console log fibonacci 10    x000D   x000D   x000D

User · Answer

Fibonacci  one-liner   function fibonacci n      return  n  lt   1    n   fibonacci n - 1    fibonacci n - 2       Fibonacci  recursive    x000D   x000D  function fibonacci number    x000D       n  lt   1 x000D    if  number  lt   0    x000D      return n  x000D      else   x000D         f n    f n-1    f n-2  x000D      return fibonacci number - 1    fibonacci number - 2   x000D      x000D     x000D   x000D  console log  f 14        fibonacci 14       377 x000D   x000D   x000D    Fibonacci  iterative    x000D   x000D   function fibonacci number    x000D       n  lt  2 x000D    if  number  lt   0    x000D      return number   x000D      else   x000D      var n   2     n   2 x000D      var fn 1   0     f n-2   if n 2 x000D      var fn 2   1     f n-1   if n 2    x000D   x000D         n  gt   2 x000D      while  n  lt   number    x000D        var aa   fn 2     f n-1  x000D        var fn   fn 1   fn 2     f n  x000D   x000D           Preparation for next loop x000D        fn 1   aa  x000D        fn 2   fn  x000D   x000D        n    x000D        x000D   x000D      return fn 2  x000D      x000D     x000D   x000D  console log  f 14        fibonacci 14       377 x000D   x000D   x000D    Fibonacci  with Tail Call Optimization    x000D   x000D  function fibonacci number    x000D    if  number  lt   1    x000D      return number  x000D      x000D   x000D    function recursion length  originalLength  previous  next    x000D      if  length     originalLength  x000D        return previous   next  x000D   x000D      return recursion length   1  originalLength  next  previous   next   x000D      x000D   x000D    return recursion 1  number - 1  0  1   x000D    x000D   x000D  console log  f 14      fibonacci 14         377 x000D   x000D   x000D

User · Answer

var a   -1  var b 0  var temp  0  var arry       for var i 1 i lt 100 i         temp   a b      a b      b temp      arry push b -1     console log arry

User · Answer

es6 - Symbol iterator and generator functions   let fibonacci           Symbol iterator              let pre   0  cur   1         for                      pre  cur       cur  pre   cur               yield cur                    for  let n of fibonacci        if  n  gt  1000          break     console log n

User · Answer

There is also a generalization of Binet s formula for negative integers   static float phi    1 0f   sqrt 5 0f     2 0f   int generalized binet fib int n       return round   pow phi  n  - cos n   M PI    pow phi  -n     sqrt 5 0f                for int i   -10  i  lt  10    i      printf   i    generalized binet fib i

User · Answer

There is no need for slow loops  generators or recursive functions  with or without caching   Here is a fast one-liner using Array and reduce   ECMAScript 6   var fibonacci  n   gt Array n  fill   reduce  a b c   gt a concat c lt 2 c a c-1  a c-2         ECMAScript 5   function fibonacci n       return Array apply null  length n   reduce function a b c  return a concat  c lt 2  c a c-1  a c-2              Tested in Chrome 59  Windows 10    fibonacci 10      0 ms - gt   10   0  1  1  2  3  5  8  13  21  34    JavaScript can handle numbers up to 1476 before reaching Infinity   fibonacci 1476      11ms - gt   1476   0  1  1  2  3  5  8  13  21  34

User · Answer

You Could Try This Fibonacci Solution Here    var a   0  console log a   var b   1  console log b   var c  for  i   0  i  lt  3  i        c   a   b    console log c     a   b   c    console log a     b   c   a    console log b

User · Answer

You re not assigning a value to z  so what do you expect y z  to do  Likewise you re never actually reading from the array  It looks like you re trying a combination of two different approaches here    try getting rid of the array entirely  and just use      Initialization of x and y as before  for  i   2  i  lt   10  i          alert x   y       z   x   y      x   y      y   z      EDIT  The OP changed the code after I d added this answer  Originally the last line of the loop was y   z  - and that makes sense if you ve initialized z as per my code   If the array is required later  then obviously that needs to be populated still - but otherwise  the code I ve given should be fine

User · Answer

You can use recursion and cache the results in a functional way    x000D   x000D  const fibonacci    n  cache    1  1  2  1     gt  x000D    cache n      cache n    fibonacci --n  cache    fibonacci --n  cache    x000D     x000D  console log fibonacci 1000    x000D  console log fibonacci 100    x000D  console log fibonacci 10    x000D   x000D   x000D

User · Answer

You should ve declared the fib variable to be an array in the first place  such as var fib      or var fib   new Array    and I think you re a bit confused about the algorithm  If you use an array to store the fibonacci sequence  you do not need the other auxiliar variables  x y z       var fib    0  1   for var i fib length  i lt 10  i          fib i    fib i-2    fib i-1     console log fib      Click for the demo  You should consider the recursive method too  note that this is an optimised version      function fib n  undefined       if fib cache n      undefined           fib cache n    fib n-1    fib n-2              return fib cache n     fib cache    0  1  1     and then  after you call the fibonacci function  you have all the sequence in the fib cache field      fib 1000   console log fib cache

User · Answer

function fib n      if  n  lt   1        return n      else       return fib n - 1    fib n - 2          fib 10      returns 55

User · Answer

I ve tried this  it might work   lt  DOCTYPE html gt   lt html lang  quot en quot  gt    lt head gt       lt meta charset  quot UTF-8 quot  gt       lt meta name  quot viewport quot  content  quot width device-width  initial-scale 1 0 quot  gt       lt title gt Fibonacci lt  title gt       lt style gt                          outline  0px              margin  0px                     input type  quot number quot                 color  blue              border  2px solid black              width  99 58vw                 lt  style gt   lt  head gt    lt body gt       lt div id  quot myDiv quot  style  quot color  white background-color  blue  quot  gt Numbers Here lt  div gt       lt input type  quot number quot  id  quot input1 quot  oninput  quot fibonacciProgram this value  quot  placeholder  quot Type Some Numbers Here quot  gt       lt script gt          function fibonacciProgram numberCount                let resultElement   document getElementById  quot myDiv quot                resultElement innerHTML    quot   quot               if  isNaN numberCount     numberCount  lt   0                    resultElement innerHTML    quot please enter a number quot                   return                            let firstBox   0              let secondBox   1              let swichBox              let entries                   entries push secondBox               while  numberCount  gt  1                    swichBox   firstBox   secondBox                  entries push swichBox                   firstBox   secondBox                  secondBox   swichBox                  numberCount--                            resultElement innerHTML   entries join                       lt  script gt   lt  body gt    lt  html gt

User · Answer

This script will take a number as parameter  that you want  your Fibonacci sequence to go   function calculateFib num        var fibArray           var counter   0       if  fibArray length    0            fibArray push              counter                    counter               fibArray push fibArray fibArray length - 1    counter        do           var lastIndex   fibArray fibArray length - 1           var snLastIndex   fibArray fibArray length - 2           if  lastIndex   snLastIndex  lt  num                fibArray push lastIndex   snLastIndex                    while  lastIndex   snLastIndex  lt  num        return fibArray

User · Answer

function fib max i j      i   i  this 0  j j  this 1     if  max   0        this push i j       max--      return fib bind this  max  j  i j         else       return this        bind  0 1   10        result    0  1  1  2  3  5  8  13  21  34  55  89

User · Answer

Here s a simple function to iterate the Fibonacci sequence into an array using arguments in the for function more than the body of the loop   fib   function numMax       for var fibArray    0 1   i 0 j 1 k 0  k lt numMax i j j x k              x i j          fibArray push x             console log fibArray      fib 10         0  1  1  2  3  5  8  13  21  34  55  89

User · Answer

Another solution could be   const fib    num    gt        if num     0  return 0      const arr  0 1       let counter 2            while counter  lt  num           arr counter  arr counter -1    arr counter -2          counter              return arr     This function returns an Array of the Fibonacci sequence based on given limit   fib 5     returns  0  1  1  2  3  5

User · Answer

If using ES2015  x000D   x000D  const fib    n  prev   0  current   1    gt  n      fib --n  current  prev   current       prev   current  console log  fib 10    x000D   x000D   x000D

User · Answer

fibonacci 1 000     10 000     100 000  Some answers run into issues when trying to calculate large fibonacci numbers  Others are approximating numbers using phi  This answer will show you how to calculate a precise series of large fibonacci numbers without running into limitations set by JavaScript s floating point implementation   Below  we generate the first 1 000 fibonacci numbers in a few milliseconds  Later  we ll do 100 000   const   fromInt  toString  add       Bignum  const bigfib   function   n   0      let a   fromInt  0    let b   fromInt  1    let     while  n  gt   0        yield toString  a          a     a   b     b   add  b         n   n - 1        console time   bigfib   const seq   Array from  bigfib  1000   console timeEnd   bigfib      25 ms  console log  seq length     1001  console log  seq       0  1  1  2  3      995 more elements     Let s see the 1 000th fibonacci number  console log  seq  1000      43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875   10 000  This solution scales quite nicely  We can calculate the first 10 000 fibonacci numbers in under 2 seconds  At this point in the sequence  the numbers are over 2 000 digits long     way beyond the capacity of JavaScript s floating point numbers  Still  our result includes precise values without making approximations   console time   bigfib   const seq   Array from  bigfib  10000   console timeEnd   bigfib      1877 ms  console log  seq length     10001  console log  seq  10000   length     2090  console log  seq  10000      3364476487     2070 more digits     9947366875   Of course all of that magic takes place in Bignum  which we will share now  To get an intuition for how we will design Bignum  recall how you added big numbers using pen and paper as a child       1259601512351095520986368     50695640938240596831104 ---------------------------                               You add each column  right to left  and when a column overflows into the double digits  remembering to carry the 1 over to the next column                           lt -001   1259601512351095520986368     50695640938240596831104 ---------------------------                        lt -472  Above  we can see that if we had two 10-digit numbers  it would take approximately 30 simple additions  3 per column  to compute the answer  This is how we will design Bignum to work  const Bignum       fromInt   n   0    gt        n  lt  10             n               n   10     Bignum fromInt  n   10  gt  gt  0         fromString   s    0     gt        Array from  s  Number   reverse         toString   b    gt        Array from  b   reverse     join           add   b1  b2    gt              const len   Math max  b1 length  b2 length        let answer            let carry   0       for  let i   0  i  lt  len  i   i   1            const x   b1 i     0         const y   b2 i     0         const sum   x   y   carry         answer push  sum   10          carry   sum   10  gt  gt  0               if  carry  gt  0  answer push  carry        return answer             We ll run a quick test to verify our example above  const x     fromString   1259601512351095520986368    const y     fromString   50695640938240596831104    console log  toString  add  x y       1310297153289336117817472   And now a complete program demonstration  Expand it to calculate the precise 10 000th fibonacci number in your own browser  Note  the result is the same as the answer provided by wolfram alpha   x000D   x000D  const Bignum   x000D      fromInt   n   0    gt  x000D        n  lt  10 x000D              n   x000D              n   10     Bignum fromInt  n   10  gt  gt  0    x000D           x000D      fromString   s    0     gt  x000D        Array from  s  Number   reverse    x000D         x000D      toString   b    gt  x000D        Array from  b   reverse     join      x000D         x000D      add   b1  b2    gt  x000D        x000D        const len   Math max  b1 length  b2 length  x000D        let answer      x000D        let carry   0 x000D        for  let i   0  i  lt  len  i   i   1    x000D          const x   b1 i     0 x000D          const y   b2 i     0 x000D          const sum   x   y   carry x000D          answer push  sum   10  x000D          carry   sum   10  gt  gt  0 x000D          x000D        if  carry  gt  0  answer push  carry  x000D        return answer x000D        x000D      x000D     x000D  const   fromInt  toString  add     x000D    Bignum x000D   x000D  const bigfib   function   n   0  x000D    x000D    let a   fromInt  0  x000D    let b   fromInt  1  x000D    let   x000D    while  n  gt   0    x000D      yield toString  a  x000D          a x000D      a   b x000D      b   add  b     x000D      n   n - 1 x000D      x000D    x000D   x000D  console time   bigfib   x000D  const seq   Array from  bigfib  10000   x000D  console timeEnd   bigfib   x000D     1877 ms x000D      x000D  console log  seq length  x000D     10001 x000D   x000D  console log  seq  10000   length  x000D     2090 x000D   x000D  console log  seq  10000   x000D     3364476487     2070 more digits     9947366875 x000D   x000D   x000D    100 000  I was just curious how far this little script could go  It seems like the only limitation is just time and memory  Below  we calculate the first 100 000 fibonacci numbers without approximation  Numbers at this point in the sequence are over 20 000 digits long  wow  It takes 3 18 minutes to complete but the result still matches the answer from wolfram alpha  console time   bigfib   const seq   Array from  bigfib  100000   console timeEnd   bigfib      191078 ms  console log  seq  length     100001  console log  seq  100000   length     20899  console log  seq  100000      2597406934     20879 more digits     3428746875

User · Answer

I think this one is simple enough to understand   function fibonacci limit        let result    0  1        for  var i   2  i  lt  limit  i              result result length    result result length - 1    result result length - 2              return result         0  1  1  2  3  5  8  13  21  34  console log fibonacci 10

User · Answer

using recursive approach and in one line     const fib   x   gt   x  lt   1   x   fib  x - 1    fib x -2       fib 15      610         display the 15 first      Array from   length  15     v  i    gt  fib i             0  1  1  2  3  5  8  13  21  34  55  89  144  233  377                     using memoization approach     function fibonacci num  memo          memo   memo              if  memo num   return memo num         if  num     0  return 0        if  num     1  return 1        return memo num    fibonacci num - 1  memo    fibonacci num - 2  memo             fibonacci 15      610         display the 15 first      Array from   length  15     v  i    gt  fibonacci i            0  1  1  2  3  5  8  13  21  34  55  89  144  233  377

User · Answer

Another easy way to achieve this   x000D   x000D  function listFibonacci n         declare the array starting with the first 2 values of the fibonacci sequence      starting at array index 1  and push current index   previous index to the array   for  var fibonacci    0  1   i   1  i  lt  n  i         fibonacci push fibonacci i    fibonacci i - 1      return fibonacci    console log   listFibonacci 10     x000D   x000D   x000D

User · Answer

function getFibonacciNumbers n            var sequence    0  1       if  n     0    n     1            return sequence n              else           for  var i   2  i  lt  n  i                   var sum   sequence i - 1    sequence i - 2               sequence push sum                 return sequence          console log getFibonacciNumbers 0    console log getFibonacciNumbers 1    console log getFibonacciNumbers 9

User · Answer

I know this is a bit of an old question  but I realized that many of the answers here are utilizing for loops rather than while loops   Sometimes  while loops are faster than for loops  so I figured I d contribute some code that runs the Fibonacci sequence in a while loop as well  Use whatever you find suitable to your needs   function fib length      var fibArr           i   0      j   1    fibArr push i     fibArr push j     while  fibArr length  lt   length        fibArr push fibArr j    fibArr i        j        i          return fibArr     fib 15

User · Answer

The golden ration  phi    n   sqrt 5  is asymptotic to the fibonacci of n  if we round that value up  we indeed get the fibonacci value   function fib n        let phi    1   Math sqrt 5   2      let asymp   Math pow phi  n    Math sqrt 5        return Math round asymp      fib 1000      4 346655768693734e 208 in just 0 62s   This runs faster on large numbers compared to the recursion based solutions

User · Answer

I like the fact that there are so many ways to create a fibonacci sequence in JS  I will try to reproduce a few of them  The goal is to output a sequence to console  like  n  6  fiboNum  8    Good  ol closure   x000D   x000D     The IIFE form is purposefully omitted  See below  x000D   x000D  const fiboGenClosure        gt    x000D    let  a  b     0  1   x000D    let n   0  x000D    return  fiboNum   a    gt    x000D       a  b     b  a   b   x000D      return   x000D        n  n    x000D        fiboNum  fiboNum x000D         x000D       x000D    x000D   x000D     Gets the sequence until given nth number  Always returns a new copy of the main function  so it is possible to generate multiple independent sequences  x000D   x000D  const generateFiboClosure   n   gt    x000D    const newSequence   fiboGenClosure    x000D    for  let i   0  i  lt   n  i      x000D      console log newSequence     x000D      x000D    x000D   x000D  generateFiboClosure 21   x000D   x000D   x000D    Fancy ES6 generator  Similar to the closure pattern above  using the advantages of generator function  and for  of loop    x000D   x000D     The  n  argument is a substitute for index  x000D   x000D  function  fiboGen n   0    x000D    let  a  b     0  1   x000D    while  true    x000D      yield  a  n     x000D       a  b     b  a   b   x000D      x000D    x000D   x000D     Also gives a new sequence every time is invoked  x000D   x000D  const generateFibonacci   n   gt    x000D    const iterator   fiboGen    x000D    for  let  value  index  of iterator    x000D      console log   x000D        n  index  x000D        fiboNum  value x000D          x000D      if  index  gt   n  break  x000D      x000D    x000D   x000D  generateFibonacci 21   x000D   x000D   x000D    Tail call recursion  This one is a little tricky  because  now in late 2018  TC optimization is still an issue  But honestly     if you don t use any smart tricks to allow the default JS engine to  use a really big numbers  it will get dizzy and claims that the next fibonacci number is  Infinity  by iteration 1477  The stack would probably overflow somewhere around iteration 10 000  vastly depends on browser  memory etc      Could be probably padded by try    catch block or check if  Infinity  was reached    x000D   x000D  const fibonacciRTC    n  i   0  a   0  b   1    gt    x000D    console log   x000D      n  i  x000D      fibonacci  a x000D        x000D    if  n     0  return  x000D    return fibonacciRTC --n    i  b  a   b   x000D    x000D   x000D  fibonacciRTC 21  x000D   x000D   x000D    It can be written as a one-liner  if we throe away the console log thing and simply return a number    x000D   x000D  const fibonacciRTC2    n  a   0  b   1    gt  n     0   a   fibonacciRTC2 n - 1  b  a   b   x000D   x000D  console log fibonacciRTC2 21   x000D   x000D   x000D    Important note   As I found out reading this mathIsFun article  the fibonacci sequence is valid for negative numbers as well  I tried to implement that in the recursive tail call form above like that    x000D   x000D  const fibonacciRTC3    n  a   0  b   1  sign   n  gt   0   1   -1    gt     x000D    if  n     0  return a   sign  x000D   return fibonacciRTC3 n - sign  b  a   b  sign   x000D    x000D   x000D  console log fibonacciRTC3 8       21 x000D  console log fibonacciRTC3 -8       -21 x000D   x000D   x000D

User · Answer

Beginner  not too elegant  but shows the basic steps and deductions in JavaScript     Array Four Million Numbers    var j       var x    1 2   var even       for  var i   1 i lt 4000001 i        j push i            Array Even Million i   1  while  i lt 4000001       var k   j i    j i-1       j i   1     k      if  k  lt  4000001           x push k                 i          var total   0  for  w in x       if  x w   2     0           even push x w                 for  num in even       total    even num      console log x   console log even   console log total

User · Answer

Here is a function that displays a generated Fibonacci sequence in full while using recursion   function fibonacci  n  length        if  n  lt  2            return  1                if  n  lt  3            return  1  1              let a   fibonacci n - 1       a push a n - 2    a n - 3        return  a length     length                 a map val   gt  console log val                  a        The output for fibonacci 5  5  will be   1 1 2 3 5   The value that is assigned to a is the returned value of the fibonacci function  On the following line  the next value of the fibonacci sequence is calculated and pushed to the end of the a array    The length parameter of the fibonacci function is used to compare the length of the sequence that is the a array and must be the same as n parameter  When the length of the sequence matches the length parameter  the a array is outputted to the console  otherwise the function returns the a array and repeats

User · Answer

Here are examples how to write fibonacci using recursion  generator and reduce    x000D   x000D   use strict  x000D   x000D    ------------- using recursion ------------ x000D  function fibonacciRecursion n    x000D    return  n  lt  2    n   fibonacciRecursion n - 2    fibonacciRecursion n - 1  x000D    x000D   x000D     usage x000D  for  let i   0  i  lt  10  i      x000D    console log fibonacciRecursion i   x000D    x000D   x000D   x000D    -------------- using generator ----------------- x000D  function  fibonacciGenerator     x000D    let a   1  x000D      b   0 x000D    while  true    x000D      yield b  x000D       a  b     b  a   b  x000D      x000D    x000D   x000D     usage x000D  const gen   fibonacciGenerator   x000D  for  let i   0  i  lt  10  i      x000D    console log gen next   value  x000D    x000D   x000D    ------------- using reduce --------------------- x000D  function fibonacciReduce n    x000D    return new Array n  fill 0  x000D       reduce  prev  curr    gt    prev 0   prev 1      prev 1   prev 0    prev 1    prev    0  1   0  x000D    x000D   x000D     usage x000D  for  let i   0  i  lt  10  i      x000D    console log fibonacciReduce i   x000D    x000D   x000D   x000D

User · Answer

You have never declared fib to be an array  Use var fib       to solve this   Also  you re never modifying the y variable  neither using it   The code below makes more sense  plus  it doesn t create unused variables    x000D   x000D  var i  x000D  var fib          Initialize array  x000D   x000D  fib 0    0  x000D  fib 1    1  x000D  for  i   2  i  lt   10  i      x000D       Next fibonacci number   previous   one before previous x000D       Translated to JavaScript  x000D    fib i    fib i - 2    fib i - 1   x000D    console log fib i    x000D    x000D   x000D   x000D

User · Answer

You can get some cache to speedup the algorithm     var tools          fibonacci   function n            var cache                   optional seed cache         cache 2    1          cache 3    2          cache 4    3          cache 5    5          cache 6    8           return execute n            function execute n                   special cases 0 or 1             if  n  lt  2  return n               var a   n - 1              var b   n - 2               if  cache a   cache a    execute a               if  cache b   cache b    execute b                return cache a    cache b

User · Answer

According to the Interview Cake question  the sequence goes 0 1 1 2 3 5 8 13 21  If this is the case  this solution works and is recursive without the use of arrays   function fibonacci n       return n  lt  1   0           n  lt   2   1           fibonacci n - 1    fibonacci n - 2      console log fibonacci 4      Think of it like this      fibonacci 4     -------- gt  2   1   3                                           -- gt  fibonacci 3    fibonacci 2                                                  ----------- 2   1   1  lt ----------  1st step - gt                                                                                                             ---- gt   fibonacci 2  -    fibonacci 1 -    Take note  this solution is not very efficient though

User · Answer

I would like to add some more code as an answer     Its never too late to code  P  function fibonacciRecursive a  b  counter  len        if  counter  lt   len            console log a           fibonacciRecursive b  a   b  counter   1  len            fibonacciRecursive 0  1  1  20     Result     0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

User · Answer

A better option would be using recursion but the following example can help you to understand logic   Edit  Correction  recursion will eventually exhaust system out of resources without archiving expected results  The following example it uses simple logic  and it can process very fast      x000D   x000D  var sequence    0 1   x000D  var range   10  x000D   x000D  for var i   0  i  lt  range-2  i     x000D      sequence push sequence i  sequence i 1    x000D    x000D   x000D  console log sequence   x000D   x000D   x000D

User · Answer

This is what I came up with    fibonacci numbers   0 1 1 2 3 5 8 13 21 34 55 89   print out the first ten fibonacci numbers  use strict   function printFobonacciNumbers n        var firstNumber   0          secondNumber   1                  fibNumbers           if  n  lt   0            return fibNumbers            if  n     1            return fibNumbers push firstNumber               if we are here we should have at least two numbers in the array     fibNumbers 0    firstNumber      fibNumbers 1    secondNumber      for  var i   2  i  lt   n  i              fibNumbers i    fibNumbers  i - 1     fibNumbers  i - 2              return fibNumbers     var result   printFobonacciNumbers 10   if  result        for  var i   0  i  lt  result length  i              console log result i

User · Answer

I just would like to contribute with a tail call optimized version by ES6  It s quite simple    x000D   x000D  var fibonacci    n  f   0  s   1    gt  n     0   f   fibonacci --n  s  f   s   x000D  console log fibonacci 12    x000D   x000D   x000D

User · Answer

I got asked this question recently  and this was my solution    x000D   x000D  function fib n    x000D    const arr    0 1      the inital array  we need something to sum at the very beginning x000D    for  let i   2  i  lt   n  i         we want the last number  so don t forget the     sign x000D      let a   arr i-1      previous Number x000D      let b   arr i-2      the one before that x000D      arr push a b      push the result x000D      x000D    return arr     if you want the n-th number  just return arr n  or arr length - 1 x000D    x000D   x000D  console log fib 4    x000D   x000D   x000D      A recursive solution would be    x000D   x000D     NOTE  This has extremly bad performance   gt  Exponential time complexity 2 n x000D   x000D  function fib n    x000D    if  n  lt  2    x000D      return n  x000D      x000D    return fib n-1    fib n-2   x000D    x000D   x000D  console log  The n-th fibonacci number     fib 6    x000D  console log  The entire fibonacci sequence      x000D   x000D     Let s see the entire fibonacci sequence x000D  for  let i   0  i  lt   6  i      x000D     console log fib i    x000D    x000D   x000D   x000D      Like mentioned earlier  the above recursive solution has a very bad impact on performance  Fortunately  there s a solution and it s called memoization    x000D   x000D     LET S CREATE A MEMO FUNCTION  x000D      and use it on the recursive   fib   function from above   x000D   x000D     We want to pass in a function which is going to  eventually   x000D     use this utility function x000D  function memo fn     x000D    const cache        x000D       let s make it reusable  and by that I mean  let s assume that x000D       we don t know the number of arguments that will be eventually passed in  x000D   return function    args    x000D     if we already call this function with the same args  x000D     YES   gt  return them x000D     if cache args      x000D       console log  cached   args 0    x000D       return cache args   x000D       x000D        otherwise  we want to call our function  x000D      the one using this  memo  function  and pass in the arguments x000D     w  the help of  apply  x000D     const res   fn apply this  args   x000D     cache args    res   x000D        we want to store the result  so later if we ll be able to x000D        return that if the args don t change x000D     console log  not cached   args 0    x000D     return res     don t forget to return the result of it    x000D     x000D    x000D   x000D     Now  let s use the memoized function  x000D     NOTE  Remember the above function has to change in a way x000D     that it calls the memoized function instead of itself x000D   x000D  function fastFib n    x000D       SAME LOGIC AS BEFORE x000D    if  n lt 2     x000D      return n  x000D      x000D     But  here is where the  magic  happens x000D     Very important  We want to call the instantiated  fibMemo  function  x000D     and NOT  fastFib   cause then it wouldn t be so fast  right       x000D    return fibMemo n-1    fibMemo n-2   x000D    x000D   x000D     DO NOT CALL IT  JUST PASS IT IN x000D  const fibMemo   memo fastFib    x000D   x000D     HERE WE WANT TO PASS IN THE ARGUMENT x000D  console log fibMemo 6    x000D   x000D   x000D

User · Answer

sparkida  found an issue with your method   If you check position 10  it returns 54 and causes all subsequent values to be incorrect  You can see this appearing here  http   jsfiddle net createanaccount cdrgyzdz 5    x000D   x000D   function     x000D     x000D  function fib n    x000D      var root5   Math sqrt 5   x000D      var val1    1   root5    2  x000D      var val2   1 - val1  x000D      var value    Math pow val1  n  - Math pow val2  n     root5  x000D   x000D      return Math floor value   0 5   x000D    x000D      for  var i   0  i  lt  100  i      x000D          document getElementById  sequence   innerHTML     0  lt  i                fib i   x000D        x000D   x000D        x000D   lt div id  sequence  gt  x000D       x000D   lt  div gt  x000D   x000D   x000D

User · Answer

A quick way to get  75  ty  geeves for the catch  I replaced Math floor for Math round which seems to get it up to 76 where floating point issues come into play         either way  I wouldn t want to be using recursion up and until that point   x000D   x000D      x000D     Binet Fibonacci number formula for determining x000D     sequence values x000D      param  int  pos - the position in sequence to lookup x000D      returns  int  the Fibonacci value of sequence  pos x000D      x000D   x000D  var test    0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 14472334024676221 23416728348467685 37889062373143906 61305790721611591 99194853094755497 160500643816367088 259695496911122585 420196140727489673 679891637638612258 1100087778366101931 1779979416004714189 2880067194370816120 4660046610375530309 7540113804746346429 12200160415121876738 19740274219868223167 31940434634990099905 51680708854858323072 83621143489848422977 135301852344706746049 218922995834555169026   x000D  var fib   function  pos    x000D          return Math round  Math pow  1   Math sqrt 5   pos   x000D              - Math pow  1 - Math sqrt 5   pos    x000D                 Math pow 2  pos    Math sqrt 5     x000D         x000D   x000D     This is only for the test    x000D  var max   test length  x000D      i   0  x000D      frag   document createDocumentFragment    x000D       div   document createElement  div    x000D       text   document createTextNode      x000D      div  x000D      text  x000D      err  x000D      num  x000D  for     i  lt  max  i      x000D      div    div cloneNode    x000D      text    text cloneNode    x000D      num   fib i   x000D      if  num     test i     x000D          err   i            test i       got     num  x000D          div style color    red   x000D        x000D      text nodeValue   i          num  x000D      div appendChild text   x000D      frag appendChild div   x000D    x000D  document body appendChild frag   x000D   x000D   x000D

User · Answer

function fibo count           when count is 0  just return      if   count  return         Push 0 as the first element into an array     var fibArr    0          when count is 1  just print and return     if  count     1            console log fibArr           return               Now push 1 as the next element to the same array     fibArr push 1          Start the iteration from 2 to the count     for var i   2  len   count  i  lt  len  i                Addition of previous and one before previous         fibArr push fibArr i-1    fibArr i-2                 outputs the final fibonacci series     console log fibArr       Whatever count we need  we can give it to above fibo method and get the fibonacci series upto the count   fibo 20     output   0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181

User · Answer

Another implementation  while recursive is very fast and uses single inline function  It hits the javascript 64-bit number precision limit  starting 80th sequence  as do all other algorithms   For example if you want the 78th term  78 goes in the last parenthesis     function  n i p r  p  p  0  r  1 i i i 1 1 return i lt  n arguments callee n i r p  r  78      will return  8944394323791464  This is backwards compatible all the way to ECMASCRIPT4 - I tested it with IE7 and it works

User · Answer

lt  DOCTYPE HTML PUBLIC  -  W3C  DTD HTML 4 01  EN   http   www w3 org TR html4 strict dtd  gt   lt html gt       lt head gt           lt meta http-equiv  Content-Type  content  text html  charset iso-8859-1  gt           lt title gt fibonacci series lt  title gt           lt script type  text javascript  gt                  function generateseries                        var fno   document getElementById  firstno   value                      var sno   document getElementById  secondno   value                      var a   parseInt fno                       var result   new Array                        result 0    a                      var b     fno                      var c   b                      while  b  lt   sno                          result push c                       document getElementById  maindiv   innerHTML    Fibonacci Series between   fno    and    sno    is    result                          c   a   b                          a   b                          b   c                                                          function numeric evt                       var theEvent   evt    window event                      var key   theEvent keyCode    theEvent which                      key   String fromCharCode key                       var regex     0-9                           if   regex test key                             theEvent returnValue   false                          if  theEvent preventDefault                               theEvent preventDefault                                                          lt  script gt           lt h1 align  center  gt Fibonacci Series lt  h1 gt       lt  head gt       lt body gt           lt div id  resultdiv  align  center  gt           lt input type  text  name  firstno  id  firstno  onkeypress  numeric event   gt  lt br gt           lt input type  text  name  secondno  id  secondno  onkeypress  numeric event   gt  lt br gt           lt input type  button  id  result  value  Result  onclick  generateseries     gt           lt div id  maindiv  gt  lt  div gt           lt  div gt       lt  body gt   lt  html gt

User · Answer

Here is another one with proper tail call   The recursive inner fib function can reuse the stack because everything is needed  the array of numbers  to produce the next number is passed in as an argument  no additional expressions to evaluate   However tail call optimization introduced in ES2015   Also one drawback is it gets the array length in every iteration  but only once  to generate the following number and getting the elements of the array upon their index  it is faster though than pop or splice or other array methods  but I did not performance tested the whole solution    x000D   x000D  var fibonacci   function len    x000D    var fib   function seq    x000D      var seqLen   seq length  x000D      if  seqLen     len    x000D        return seq  x000D        else   x000D        var curr   seq seqLen - 1   x000D        var prev   seq seqLen - 2   x000D        seq seqLen    curr   prev  x000D        return fib seq   x000D        x000D      x000D    return len  lt  2    0    fib  0  1    x000D    x000D   x000D  console log fibonacci 100    x000D   x000D   x000D

User · Answer

Yet another answer would be to use es6 generator functions   function  fib       var current   a   b   1     yield 1     while  true        current   b       yield current       b   a   b      a   current         sequence   fib    sequence next       1 sequence next       1 sequence next       2

[javascript] Generating Fibonacci Sequence

Examples related to javascript

Examples related to fibonacci