关于javascript:面试官用尾递归优化斐波那契函数

1 前言

编程题：输出一个整数 n，输入 斐波那契数列 的第 n 项

有些面试官喜爱问这道题。可能你感觉这太简略了，用递归或递推一下子就实现了。

正当你信念满满用了两种形式实现的时候 …

面试官：当初请用“尾递归”优化你的递归实现，用“ES6 解构赋值”优化你的递推实现

…

这时候如果你的基本功不扎实，可能你就懵了。

就是这么简略的一道题，蕴含着相当多的 JS 知识点，尤其是它的 优化过程 能够看出你的基本功扎不扎实，所以有些面试官喜爱问这道题。

上面咱们来看递归和递推这两种实现以及它们各自的优化过程

2 递归和尾递归

2.1 递归实现

先来看递归实现：

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

来看看这段代码有什么问题

第一个问题很容易看进去，就是当 n 十分大的时候，递归深度过大导致栈内存溢出，即“爆栈”

第二个问题就是有相当多的反复计算，比方：

fibonacci(7)
= fibonacci(6) + fibonacci(5) // 这里计算了 f(5)，上面又计算了一次 f(5)
= (fibonacci(5) + fibonacci(4)) + (fibonacci(4) + fibonacci(3)) // 这里计算了两次 f(5)
...

2.2 尾调用

在解决下面两个问题之前，先来理解一下什么是 尾调用

尾调用：一个函数里的最初一个动作是返回一个函数的调用后果，即最初一步新调用的返回值被以后函数返回

比方：

function f(x) {return g(x)
}

上面这些状况不属于尾调用：

function f(x) {return g(x) + 1 // 先执行 g(x)，最初返回 g(x)的返回值 +1
}

function f(x) {let ret = g(x) // 先执行了 g(x)
  return ret // 最初返回 g(x)的返回值
}

2.3 尾调用打消（尾调用优化）

一个函数调用时，JS 引擎会创立一个新的栈帧并将其推入调用栈顶部，用于示意该次函数调用

当一个函数调用产生时，计算机必须“记住”调用函数的地位——返回地位，才能够在调用完结时带着返回值回到该地位，返回地位个别保留在调用栈上。

在 尾调用 这种非凡情景中，计算机实践上能够不须要记住尾调用的地位，而从被调用的函数间接带着返回值返回以后函数的返回地位（相当于间接间断返回两次）

如下图：因为尾调用，实践上能够不记住地位 2，而从函数 g 间接带着返回值返回到地位 1（即函数 f 的返回地位）

因为尾调用之前的工作曾经实现了，所以以后函数帧（即调用时创立的栈帧）上蕴含局部变量等等大部分的货色都不须要了，以后的函数帧通过适当的变动当前能够间接当做尾调用的函数的帧应用，而后程序就能够跳到被尾调用的函数。

用上图中的例子来解释就是，函数 f 尾调用函数 g 之前的工作曾经实现了，所以调用函数 f 时创立的函数帧间接给函数 g 用了，就不须要从新给函数 g 创立栈帧。

这种函数帧变动重复使用的过程就叫做 尾调用打消 或尾调用优化

2.4 尾递归

如果函数在尾调用地位调用本身，则称这种状况为 尾递归。尾递归是一种非凡的尾调用，即在尾部间接调用本身的递归函数

因为尾调用打消，使得尾递归只存在一个栈帧，所以永远不会“爆栈”。

ES6规定了所有 ECMAScript 的实现都必须部署“尾调用打消”，因而在 ES6 中只有应用 尾递归，就不会产生栈溢出

2.5 尾递归优化斐波那契函数

回到 2.1 中斐波那契函数存在的两个问题，能够应用 尾递归 来解决“爆栈”的问题

须要留神的是：ES6 的尾调用打消只在严格模式下开启

为了让原来的递归函数变成尾递归，须要改写函数，让函数最初一步调用本身

// 原递归函数
function fibonacci(n) {if (n === 0 || n === 1) {return n;}
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// 批改后
'use strict'
function fibonacci(n, pre, cur) {if (n === 0) {return n;}
  if (n === 1) {return cur;}
  return fibonacci(n - 1, cur, pre + cur);
}
// 调用
fibonacci(6, 0, 1)

批改后的计算逻辑是这样的：

f(6, 0, 1) 
= f(5, 1, 0 + 1) 
= f(4, 1, 1 + 1) 
= f(3, 2, 1 + 2) 
= f(2, 3, 2 + 3)
= f(1, 5, 3 + 5)
= 8

你可能曾经发现了，事实上这就是递推，从 0 + 1 开始计算，始终到第 n 项

另外，能够应用 ES6 的默认参数来让函数只传入一个参数 n 即可

'use strict'
function fibonacci(n, pre = 0, cur = 1) {if (n === 0) {return n;}
  if (n === 1) {return cur;}
  return fibonacci(n - 1, cur, pre + cur);
}
fibonacci(6)

此外，因为函数改成了尾递归的模式，第 f(n) 只与 f(n-1) 无关，大量反复计算的问题也失去了解决

3 递推

递推实现

function fibonacci(n) {
  let cur = 0;
  let next = 1;
  for (let i = 0; i < n; i++) {
    let temp = cur;
    cur = next;
    next += temp;
  }
  return cur;
}

递推在性能上没啥好优化的，然而咱们能够在模式上进行优化

利用 ES6 的解构赋值能够省去两头变量

function fibonacci(n) {
  let cur = 0;
  let next = 1;
  for (let i = 0; i < n; i++) {[cur, next] = [next, cur + next]
  }
  return cur;
}

公众号【前端嘛】