面试官:用“尾递归”优化斐波那契函数

更新日期: 2021-11-04阅读: 953标签: 面试

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;
}

原文链接:https://www.cnblogs.com/bidong/archive/2021/11/04/15507032.html

链接: https://fly63.com/article/detial/10774

Web前端年后跳槽面试复习指南

很多童鞋可能年后有自己的一些计划,比如换份工作环境,比如对职业目标有了新的打算。当然面试这一关不得不过,大概又不可能系统性的复习,这里罗列一些 重点 面试的知识点和文章,

前端面试之webpack面试常见问题

什么是webpack和grunt和gulp有什么不同?什么是bundle,什么是chunk,什么是module?什么是Loader?什么是Plugin?如何可以自动生成webpack配置?webpack-dev-server和http服务器如nginx有什么区别?

每个 JavaScript 工程师都应当知道的 10 个面试题

多问问应聘者高层次的知识点,如果能讲清楚这些概念,就说明即使应聘者没怎么接触过 JavaScript,也能够在短短几个星期之内就把语言细节和语法之类的东西弄清楚。

37个JavaScript基本面试问题和解答

面试比棘手的技术问题要多,这篇文章整理了37个JavaScript基本面试问题和解答,这些仅仅是作为指导。希望对前端开发的你有所帮助!

React常见面试题

React常见面试题:React中调用setState之后发生了什么事情?React中Element与Component的区别?优先选择使用ClassComponent而不是FunctionalComponent?React中的refs属性的作用是什么?React中keys的作用是什么?

有趣的Js面试题_如何让 (a == 1 && a == 2 && a == 3) 返回 true

题目大意为:JS 环境下,如何让 a == 1 && a == 2 && a == 3 这个表达式返回 true ?这道题目乍看之下似乎不太可能,因为在正常情况下,一个变量的值如果没有手动修改,在一个表达式中是不会变化的。

js练习笔记:10道JavaScript题目

10道JavaScript题目:累加函数addNum、实现一个Person类、实现一个arrMerge 函数、实现一个toCamelStyle函数、setTimeout实现重复调用、实现一个bind函数、实现一个Utils模块、输出一个对象自身的属性

vue菜鸟从业记:没准备好的面试,那叫尬聊

面试开场白总缺少不了自我介绍,一方面是面试官想听听你对自己的介绍,顺便有时间看看简历上的描述,是否与口述一致。另一方面就是看看你简历上做过什么项目,用到了哪些技术栈,一会儿好提问你。

毕业一年左右的前端妹子面试总结

把面试当做学习,这个过程你会收益很大。前端知识很杂,可能实际工作中用到的技术,像框架都是跟着公司的要求走的,像我最近也在看React啦,Vue和React都对比着再学习

vue面试时需要准备的知识点

vue上手可以说是比较轻松而且简单,如果你用过angular,react,你也会很喜欢vue。vue的核心思想依旧是:构建用户界面的渐进式框架,关注视图的变化。这也是为什么新建的文件是结构是template script style

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!