记录不使用递归的斐波那契数列

用普通的递归法会爆栈的原因是栈内存一般比较小, 而使用递归通常会向调用栈内加入大量的待调用函数, 超过调用栈的大小(操作系统给应用程序分配的栈内存大约是8M), 就会出现经典的 stack overflow 错误了

下面是一个递归调用的经典案例, 求斐波那契数列的第n项

function recurFib(n) {
  if (n < 2) {
    return n
  } else {
    return recurFib(n-1) + recurFib(n-2)
  }
}

可以看到, 只要不满足 n < 2 这个条件是, 这个函数每次调用都会重复 return 自身, 这样就会让调用栈内重复加入这个函数的调用.

在不使用递归的前提下, 可以使用数组记录数列每一项的值
相当于用数组的记录代替了js本身的call stack

function fib(n) {
  if (n < 1) throw new Error('n must > 0')
  const arr = []
  for (let i = 0; i < n; i ++) {
    arr[i] = 0
  }
  if (n == 1 || n == 2) {
    return 1
  } else {
    // 这里生成全部的数组
    arr[0] = 1
    arr[1] = 1
    for (let i = 2; i < n; i++) {
      arr[i] = arr[i-1] + arr[i-2]
    }
    console.log(arr)
    return arr[n-1]
  }
}

仔细看来, n = 1 和 n = 2 的请客也是不必要的, 因为这个数组里面已经涵盖了这些结果
再精简一下

function fib(n) {
  if (!n) throw new Error('fuck')
  if (n < 1) throw new Error('n must > 0')
  const arr = []
  for (let i = 0; i < n; i ++) {
    arr[i] = 0
  }
  arr[0] = 1
  arr[1] = 1
  for (let i = 2; i < n; i++) {
    arr[i] = arr[i-1] + arr[i-2]
  }
  return arr[n-1]
}

再加一个迭代法

function fib(n) {
  if (!n) throw new Error('fuck')
  if (n < 1) throw new Error('fuck, n must > 0')
  let first = 1
  let second = 1
  let index = 2
  let target = 1
  while(index < n) {
    target = first + second
    first = second
    second = target
    index += 1
  }
  return target
}