斐波那契序列 算法 头条腾讯前端面经

算法题目

实现一个函数算法,计算斐波那契数列第n个数是多少?

斐波那契数列是这样的序列:
1 1 2 3 5 8 13 21 34 55 89 …
第一个和第二个都是 1
第n个数是第n-1个数和第n-2个数之和

问题是给定n,求出第n个数是多少

算法详解

这是一道很经典的算法题,关于斐波那契数列的

仔细观察,知道斐波那契序列的数都是前两个数之和,即 f(n) = f(n-1) + f(n-2)

我们来实现两个版本,一个递归版本、一个非递归版本

递归版本大概代码如下:

1
2
3
4
5
6
7
function fibonacci(n) {
if (n === 1 || n === 2) {
return 1
}

return fibonacci(n - 1) + fibonacci(n - 2)
}

递归版本看起来非常简洁,但是递归也有一些弊端,一不小心可能导致栈爆了

再来看看非递归版本的大概代码:

1
2
3
4
5
6
7
8
9
10
11
12
function fibonacci(n) {
if (n === 1 || n === 2) {
return 1
}

let [pre, cur] = [1, 1]
for (let i = 3; i <= n; ++ i) {
[pre,cur] = [cur, pre + cur];
}

return cur
}

非递归版本看起来没有递归版本那么清晰,但是非递归版本比递归版本安全稳定效率高一些
关键点思想在于每次都把n - 1 和 n - 2缓存下了,计算 n 只要把前面两个值相加即可

自己仔细琢磨下这两个代码吧

类似斐波那契序列的阶梯算法 – 头条面试题

 
更多前端面试题和算法题,请搜索微信小程序 前端面试精华
Front-end interview essence
Front-end interview essence

坚持原创技术分享,您的支持将鼓励我继续创作!