js基础：递归，迭代，和尾调用优化

面试 futu 遇到的问题

场景

今天去面试 futu, 被问到一题 -> 参数为数字, 输出斐波那契数列对应结果, 实现了一下

function fibonacci(n) {
  if (n == 1 || n == 2) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

然后面试官问: "你觉得这个有什么问题 ?"
我: "(⊙o⊙)…忘记判断参数类型了."
面试官: "不是这个问题."
我: "嗯..嗯...嗯.呃...这个..."
面试官: "如果数字很大会怎么样?"
我: "会...性能很差"
面试官: "嗯, 会爆炸, 为什么? 那怎么改?"
我: "嗯..嗯...嗯.呃...不会..."
面试官: "你回去查一下吧."

Game Over

回来查

原来 有个概念叫尾调用优化, 果然还是太菜

什么是尾调用

尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。尾调用-阮一峰

尾调用之所以与其他调用不同，就在于它的特殊的调用位置。
我们知道，函数调用会在内存形成一个”调用记录”，又称”调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数 A 的内部调用函数 B，那么在 A 的调用记录上方，还会形成一个 B 的调用记录。等到 B 运行结束，将结果返回到 A，B 的调用记录才会消失。如果函数 B 内部还调用函数 C，那就还有一个 C 的调用记录栈，以此类推。所有的调用记录，就形成一个”调用栈”（call stack）。

递归的计算过程（recursive process）包含了两个阶段，先逐级扩展（expansion），构造起一个由被推迟的操作组成的链条（会被解释器保存在堆栈里），然后在收缩（contraction）阶段逐级回溯执行那些操作。随着递归计算步骤的增多，这种方法消耗的资源会越来越大，而且会包含越来越多的冗余操作，上面那个求斐波那契数列的例子（在 SICP 里被称作“树形递归”）在这方面问题尤其严重，因为它的计算步骤会随着参数而指数性的增长。

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。

看完浏览器原理，简言之，尾递归不用保留上一步的执行上下文，节省了内存。

优化->尾调用

function lastFibonacci(n, acc1, acc2) {
  if (n == 1) return acc1
  return lastFibonacci(n - 1, acc2, acc1 + acc2)
}

lastFibonacci(6, 1, 1) //8
lastFibonacci(7, 1, 1) //13

这样每次都要输入 1,1,可以用柯里化或 es6

加柯里化或 es6

// 再封装一层柯里化-----------
function curringF(acc1, acc2) {
  return function (n) {
    return lastFibonacci(n, acc1, acc2)
  }
}

let func = curringF(1, 1)
func(6) // 8
func(7) // 13

//或 es6---------
function lastFibonacci(n, acc1 = 1, acc2 = 1) {
  if (n == 1) return acc1
  return lastFibonacci(n - 1, acc2, acc1 + acc2)
}
lastFibonacci(7) //13

虽然解决了占用内存的问题，但是冗余计算还是在的。

递归和迭代的区别

• 迭代

// 迭代，重复一定的算法，上一次的结果作为达到想要的目的。数学上二分法，牛顿法是很好的迭代例子
function iteration(x) {
  var sum = 1
  for (x; x >= 1; x--) {
    sum = sum * x
  }
}

• 递归

// 递归，自身调用自身的迭代就是递归。
// 但是正式定义好像不是这么说的。这只是我个人理解
function recursion(x) {
  if (x > 1) {
    return x * recursion(x - 1)
  } else {
    return 1
  }
}

相同点：

递归和迭代都是循环的一种。递归和迭代都用了循环这个手段。

不同点：

• 程序结构不同

递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环。 其中，迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。

• 算法结束方式不同

递归循环中，遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。 当然很多情况都是多种循环混合采用，这要根据具体需求。

• 效率不同

在循环的次数较大的时候，迭代的效率明显高于递归，因为递归需要保留着上一次的执行环境，在后代得到结果之后需要回溯。递归可能存在冗余计算（比如最典型的是斐波那契数列，计算第 6 个需要计算第 4 个和第 5 个，而计算第 5 个还需要计算第 4 个，所处会重复）。迭代在这方面有绝对优势。