JS for Fibonacci sequence

Fibonacci sequence

The first number is 0, The second term is 1, Each subsequent number is the sum of the first two numbers

//  recursive O(2^n)
function fibonacci(n){
    
  if(n<=0) return 0
  if(n===1) return 1
  return fibonacci(n-1) + fibonacci(n-2)
}

Optimize

• No recursion 、 Use the cycle
• Record intermediate results
• The time complexity is O(n)

// O(n)
function fibonacci(n){
    
  if(n<=0) return 0
  if(n===1) return 1

  let n1 = 1 //  Record n-1 Result 
  let n2 = 0 //  Record n-2 Result 
  let res = 0
  for(let i =2 ;i<=n;i++){
    
    res = n1+n2
    //  Record intermediate results 
    n2 = n1
    n1 = res
  }
  return res
}

Dynamic programming

• Use recursive thinking to analyze problems , Solve problems with loops