个人评价：经典递归题，但可能会写出超时代码，另需注意简化空间复杂度，可引入动态规划思想~
题目难度：🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）
另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章
斐波那契数列
题目描述
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e^9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
解题思路
我们先考虑 n<10，则可快速写出代码如下：
func fib(n int) int {
if n < 2 {
return n
}
return (fib(n-1)+fib(n-2))%1000000007
}
但，如果提交此代码至 LeetCode，就超时了 🙂
敲黑板，递归极容易出现大量重复计算，如何改善？
🙌 记下来 =》记忆化递归
下图帮助理解递归法的 “重复计算” 概念（来自 LeetCode 精选题解附图）
改良后的 「记忆化递归」代码如下：
func fib(n int) int {
if n < 2 {
return n
}
record := []int{0, 1}
var next int
for i := 2; i <= n; i++ {
next = record[i-1] + record[i-2]
record = append(record, next%1000000007)
}
return record[n]
}
时间复杂度 & 空间复杂度？
🙌 时间复杂度 O(n) ，额外的空间复杂度 O(n)
继续改善，是否可降低空间复杂度？
🙌 没必要记录为 []int，只需记下两个值变量即可 => O(1)
func fib(n int) int {
if n < 2 {
return n
}
prev, curr := 0, 1
for i := 2; i <= n; i++ {
prev, curr = curr, (prev+curr)%1000000007
}
return curr
}
https://play.golang.org/p/kFaigSWCfrG
题目引申
引入「动态规划」的思想解题（算是最简单的 DP 题了😁），如下（参考 LeetCode 题解）：
总结
斐波那契真的是老面试题了，也是递归的经典示例。但面试的时候，快速手写出清晰可读性强的代码也并不简单。
截图下来 =》面试临时抱佛脚 😁
另外，代码实操部分，若写了递归 ，注意限制递归深度！！！
面试中，可能问到递归相关的实操问题，如平时有写递归么？有什么规范？不同语言的递归深度限制？blabla …
扩展动态规划，有兴趣的继续刷题鸭~ 70. 爬楼梯 就决定是你了=》下一篇