面试常考算法题系列写到第八篇这一次轮到斐波那契数列。如果你正在准备Java后端、C开发或者前端算法面试大概率遇到过这个题写一个函数输入n输出斐波那契数列的第n项。题目看着简单但面试官会用各种方式加码从递归到动态规划再到矩阵快速幂一路追问下来能过滤掉一大半只会背答案的候选人。我会结合自己在平时刷题和模拟面试中反复见过的思路把斐波那契数列涉及的递归、记忆化、递推、快速幂、取模、大数处理都过一遍并给出可直接套用的代码和避坑经验。无论是刚接触算法题的新手还是准备冲刺高难度的进阶选手这篇内容都能帮你把这类题吃透。1. 面试中的斐波那契从兔子问题到递归考察1.1 面试官为什么爱考这个看似简单的数列斐波那契数列的定义很简单F(0)0、F(1)1之后每一项都是前两项之和。但它背后牵扯的东西不少递归边界、重复子问题、动态规划、状态压缩、矩阵运算、对数级复杂度、甚至数论中的循环周期。面试官问一道斐波那契表面看是考你“能不能把递归写对”实际上可以顺着你给出的解法一路追问到算法复杂度、空间优化、数学建模甚至工程上的溢出和取模处理。也就是说一道题能在一轮面试里同时覆盖多块能力性价比极高。从我辅导和刷题的经验看很多候选人一上来就写递归然后被问“复杂度是多少”就卡住也有一部分人能写动态规划但把n0和n1的边界搞错能主动想到矩阵快速幂的人更少。所以不要小看这道题它在不同层级候选人之间区分度明显。面试官并不期待你背出所有解法而是想看你遇到问题时的思考路径和代码风格。你哪怕只会递归只要能把指数级复杂度和重复计算问题说清楚也能拿到不错的评价。1.2 斐波那契的常见面试变形题在真实面试中题目很少直接写成“求斐波那契数列第n项”而是套一层场景。最经典的是青蛙跳台阶一只青蛙一次可以跳上1级台阶也可以跳上2级求跳上n级台阶有多少种跳法。仔细推导就会发现跳到第n级可以从第n-1级跳1步也可以从第n-2级跳2步所以dp[n] dp[n-1] dp[n-2]本质上就是斐波那契。还有矩形覆盖、兔子繁殖、爬楼梯、用1x2骨牌铺2xn矩形等问题建模后都是同一个递推式。遇到这类变形题第一反应不是套公式而是先定义状态。把“跳到第n级的方法数”想清楚递推关系自然就出来了。面试官很喜欢通过这种包装题来观察候选人能不能从实际问题中抽象出数学模型。如果你能指出“这就是斐波那契”并且顺手把边界条件说清楚基本就稳了。这里要注意青蛙跳台阶的边界通常和斐波那契略有区别比如f(1)1、f(2)2所以必须结合题目描述重新确认初始值不要想当然直接套F(0)0、F(1)1。1.3 先搞清楚题目的边界定义斐波那契数列有两种常见定义一种是从第0项开始F(0)0、F(1)1另一种是从第1项开始F(1)1、F(2)1。不同题目、不同语言变体差异很大。如果题目没说明可以先向面试官确认n的范围和起始项这是加分的严谨表现。写代码时也要明确n0和n1的返回值否则很容易在边界测试用例上翻车。另外要注意返回值类型。斐波那契增长非常快F(50)已经超过125亿F(100)大约3.54e20远超32位整数范围。如果题目要求输出int可能需要取模如果是Java面试需要考虑int溢出如果题目明确允许使用大数可以用BigInteger。工程上常见做法是让结果对1e97取模或者使用long long并加上范围限制。千万不要等到测试用例跑出负数才意识到溢出主动提出n的约束和取模方案会让面试官觉得你很有工程意识。2. 三种常规解法的演进递归、备忘录、动态规划2.1 暴力递归写起来最快死得也最快先看最直接的写法public int fib(int n) { if (n 0) return 0; if (n 1) return 1; return fib(n - 1) fib(n - 2); }能跑通小数据但如果面试官追问时间复杂度就不太好答了。这里涉及到指数复杂度分析每次调用fib(n)会继续调用fib(n-1)和fib(n-2)形成一棵“递归调用树”。假设时间复杂度为T(n)则T(n)T(n-1)T(n-2)O(1)很容易推导出T(n)O(2^n)。这里的指数增长不是2的n次方那么严格实际上是黄金比例约1.618的n次方但口头分析直接说指数级即可。空间复杂度取决于递归栈深度是O(n)。实际测试会发现n40左右已经明显卡顿n50可能要等很久。原因是有大量重复子问题比如fib(5)会重复计算fib(3)很多次。面试时如果只写这种解法一定要主动说出它的缺点和优化方向千万不要停下来等面试官提示。你主动说“这版会有大量重复计算我们可以加备忘录”会显得思路清晰。提示用递归开头展示思路没问题但一定不要停在递归主动往后讲这是面试中的常见加分点。2.2 备忘录递归用空间换时间优化思路很简单计算过的结果存起来下次直接查。自顶向下加一个数组或者哈希表作为缓存。public int fib(int n) { int[] memo new int[n 1]; return dfs(n, memo); } private int dfs(int n, int[] memo) { if (n 0) return 0; if (n 1) return 1; if (memo[n] ! 0) return memo[n]; memo[n] dfs(n - 1, memo) dfs(n - 2, memo); return memo[n]; }这里有一个小坑memo数组初始值都是0如果F(0)也是0那么memo[0]0无法区分“没计算过”和“结果是0”。幸好我们已经在n0时直接返回0不会去查memo[0]所以逻辑没有问题。但如果改成从1开始、F(1)F(2)1最好用-1初始化memo代表未计算。这种细节面试官会看在眼里。时间复杂度降到了O(n)因为每个n最多计算一次空间复杂度O(n)包括递归栈和缓存数组。备忘录递归最大的优点是代码结构接近递归思考成本低但还存在栈深度问题n达到10万时可能栈溢出。如果题目范围很小这是最不容易错的解法。2.3 自底向上递推与滚动变量优化更稳妥的做法是自底向上动态规划。既然斐波那契只依赖前两项完全可以不用保存整个数组。可以用两个变量循环滚动。public long fib(int n) { if (n 0) return 0; if (n 1) return 1; long prev2 0; long prev1 1; for (int i 2; i n; i) { long cur prev1 prev2; prev2 prev1; prev1 cur; } return prev1; }这个版本时间O(n)空间O(1)是面试中最稳妥也最推荐的主流答案。如果题目要求取模只需要在cur这一行加上模运算即可。注意循环从2开始n0和n1已经提前返回。如果你担心n是负数可以在一开始判断并抛出异常这也体现了代码的健壮性。面试中如果你想展示对动态规划的理解可以把“状态定义”说清楚dp[i]表示第i项的值转移方程dp[i]dp[i-1]dp[i-2]。虽然斐波那契太简单但这是动态规划思想的雏形。很多动态规划难题的思维路径和这个题一模一样先暴力递归、再备忘录、再自底向上最后优化空间。所以这个题非常适合作为面试者表达能力的分水岭。2.4 面试中如何选择和表述我建议的回答顺序是先提递归解释指数级复杂度紧接着说可以用备忘录优化到O(n)然后说改成自底向上和滚动变量空间降到O(1)。这样一套流程讲下来几乎覆盖了“算法设计”的完整故事。面试官如果继续深挖再考虑矩阵快速幂。不要一上来直接写矩阵快速幂除非题目明确要求超大n否则会显得为了炫技而忽略了常规思考过程。实际面试中面试官更看重你有没有“边做边思考”的习惯。你可以先问“n大概多大期望复杂度是什么”如果对方说n可以达到10^18那必然不能用O(n)而是要用快速幂。如果n是100以内O(n)就是最优解没必要上矩阵。这种问题驱动的思考方式比背模板有用得多。3. 矩阵快速幂把复杂度压到 O(log n)3.1 斐波那契为什么能用矩阵表示当题目要求n很大比如10^9、10^18常规O(n)就太慢了。这时候要用矩阵快速幂。核心点在于斐波那契递推可以写成矩阵乘法形式。考虑向量 [F(n1), F(n)]^T可以由 [F(n), F(n-1)]^T 乘一个矩阵得到[F(n1)] [1 1] [F(n) ] [F(n) ] [1 0] [F(n-1)]把这个矩阵记为M那么就有[F(n1), F(n)]^T M^n * [F(1), F(0)]^T所以求F(n)等价于求矩阵M的n次方。快速幂能把幂运算从O(n)降到O(log n)因此整体复杂度是O(log n)。这里需要说明矩阵乘法本身是常数时间2x2矩阵所以复杂度只取决于幂运算的步骤数。如果直接乘n次M复杂度还是O(n)等于白干快速幂本质上是通过指数的二进制分解把连乘过程压缩成log n次矩阵乘法。很多同学看到“矩阵”就想绕开其实2x2矩阵乘法只需要4个变量比想象中简单。你只要记住结果矩阵四个位置的计算公式就能手写出来。面试中如果推到这一步已经能拿到相当高的加分。3.2 快速幂实现细节与模板代码先定义一个2x2矩阵的乘法。用Java写一个完整版本public class FibonacciMatrix { static long[][] mul(long[][] a, long[][] b, long mod) { return new long[][]{ {(a[0][0]*b[0][0] a[0][1]*b[1][0]) % mod, (a[0][0]*b[0][1] a[0][1]*b[1][1]) % mod}, {(a[1][0]*b[0][0] a[1][1]*b[1][0]) % mod, (a[1][0]*b[0][1] a[1][1]*b[1][1]) % mod} }; } static long[][] pow(long[][] base, long power, long mod) { long[][] res {{1,0},{0,1}}; while (power 0) { if ((power 1) 1) res mul(res, base, mod); base mul(base, base, mod); power 1; } return res; } static long fib(long n, long mod) { if (n 0) return 0; if (n 1) return 1; long[][] base {{1,1},{1,0}}; long[][] m pow(base, n - 1, mod); return m[0][0]; } }这里最关键的是初始矩阵的幂次和返回值一定要根据F(0)和F(1)的定义验证一遍。以上面代码为例我们设F(0)0、F(1)1想求F(n)等价于 [F(n), F(n-1)]^T M^(n-1) * [F(1), F(0)]^T因此结果是M^(n-1)的左上角也就是m[0][0]。如果面试题用的是F(1)1、F(2)1那求F(n)可能要调整成M^(n-1)或M^n这里最容易出错。最稳妥的办法是用小n先自测一遍比如n2、n3确认结果等于1和2。快速幂的模板和普通整数快速幂几乎一样只是把整数乘法替换成矩阵乘法。你只要掌握这个抽象以后扩展到K阶斐波那契、线性递推都是一套逻辑。面试官如果问“为什么复杂度是O(log n)”你回答“每次循环指数右移一位最多log n次每次只做常数次矩阵乘法”就足够清晰了。3.3 面试追问能不能扩展到任意线性递推如果这题是加试面试官可能会追问给定递推式 f(n)af(n-1)bf(n-2)又或者更高阶怎么办思路是一样的把状态向量扩展。对于二阶递推状态向量是[f(n), f(n-1)]转移矩阵就是[[a, b], [1, 0]]。对于更高阶比如三阶递推状态向量取[f(n), f(n-1), f(n-2)]转移矩阵是[[a, b, c], [1,0,0], [0,1,0]]依此类推。能说到这一步说明你理解了状态空间的概念不是死记矩阵模板。再进一步如果面试官聊到“矩阵快速幂还能解决哪些问题”可以提到常系数齐次线性递推、图的邻接矩阵幂、马尔可夫链状态转移、计数的线性递推等。不过面试中点到为止不要硬往远处扯。重点是把“递推关系转化成矩阵转移”这个思想讲清楚。4. 通项公式、取模与工程化细节4.1 黄金分割通项公式能不能直接用斐波那契还有一个著名的通项公式叫比内公式F(n) (1/sqrt(5)) * (((1sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)理论上可以直接套公式用Math.pow计算。但用它求整数结果有两个问题第一浮点数运算有精度损失n稍大一点四舍五入后可能差1第二如果要取模公式里的无理数没法直接模运算。所以在工程和面试中这个公式基本只适合快速估算斐波那契增长速度或者用来证明时间复杂度是黄金比例的指数级不建议作为最终算法。如果面试官问“你听说过通项公式吗”你可以大方承认并补一句“但它有精度问题一般题目不会用除非n很小”。这种回答既展示了知识面又体现了工程判断力。有些候选人知道越多越爱炫结果在精度问题上翻车没必要。4.2 大数场景与取模处理实际工程题里经常要求结果对一个大质数取模比如1e97或1e99。原因是避免溢出同时模大质数可以配合数论算法。取模时要注意加法运算的写法先分别取模再加再取模。原因是两个取过模的值相加仍然可能超过long范围尤其当模数接近1e18时。一般1e97比较安全两个1e97相加不超过2e9远小于int上限但安全起见还是用long。如果模数本身很大就需要每一步取模。另外如果不需要取模而n在50到100之间C和Java都要注意数据类型。C用long long可以支撑到F(92)左右再大就要用大数库。Java用long同样到F(92)超过之后可以用BigInteger但要注意BigInteger运算慢得多。Python则没有这个烦恼整数自动扩容但速度也会下降。建议在代码里显式处理大数先判断题目范围再决定用long、BigInteger还是取模。4.3 皮萨诺周期面试加分项当题目既要取模又需要重复多次查询时有一个数论性质可以优化斐波那契数列对模m取模后结果是周期性的这个周期叫皮萨诺周期。比如模10时周期是60模1e97时周期会非常大往往不是我们需要的。不过在特定场景下比如m10、m100可以先求出周期把n压缩到周期内然后再用O(n)计算查询复杂度能大幅下降。面试中能提到皮萨诺周期是明显的加分项但要注意不要展开过深。你只需要说“如果模数比较小可以先预处理出循环节把n取模到循环节内再O(1)或O(周期)回答查询”面试官就会认可你知识面。实际操作中1e97这种大模数的周期太大预处理不现实所以这个技巧只适合小模数或预计算场景。5. 代码实现Java、C、Python三种语言的实战版本5.1 Java实现完整示例结合前面的分析给一个比较完整的Java版本包含常规递推和矩阵快速幂取模方便直接复用public class Fibonacci { public int fib(int n, int mod) { if (n 0) throw new IllegalArgumentException(n must be non-negative); if (n 0) return 0; if (n 1) return 1; int a 0, b 1; for (int i 2; i n; i) { int c (a b) % mod; a b; b c; } return b; } public long fibMatrix(int n, long mod) { if (n 0) throw new IllegalArgumentException(n must be non-negative); if (n 0) return 0; if (n 1) return 1; long[][] base {{1, 1}, {1, 0}}; long[][] result matrixPow(base, n - 1, mod); return result[0][0]; } private long[][] matrixMul(long[][] a, long[][] b, long mod) { return new long[][]{ {(a[0][0] * b[0][0] a[0][1] * b[1][0]) % mod, (a[0][0] * b[0][1] a[0][1] * b[1][1]) % mod}, {(a[1][0] * b[0][0] a[1][1] * b[1][0]) % mod, (a[1][0] * b[0][1] a[1][1] * b[1][1]) % mod} }; } private long[][] matrixPow(long[][] base, long power, long mod) { long[][] res {{1, 0}, {0, 1}}; while (power 0) { if ((power 1) 1) res matrixMul(res, base, mod); base matrixMul(base, base, mod); power 1; } return res; } }这段代码里矩阵幂返回的是M^(n-1)的左上角。如果你把n改成小值验证例如fibMatrix(2)应该等于1。Java中注意不要在long乘法时忽略溢出尤其在mod很大时a[0][0]*b[0][0]可能超过long上限。不过常见面试题mod1e97时两个1e97相乘约1e18小于Long.MAX_VALUE约9.22e18所以安全。5.2 C实现完整示例C的写法和Java很像区别在于直接用long long类型并且定义结构体会方便一些#include cstdint #include stdexcept struct Matrix { int64_t a00, a01, a10, a11; }; Matrix mul(Matrix x, Matrix y, int64_t mod) { return { (x.a00 * y.a00 x.a01 * y.a10) % mod, (x.a00 * y.a01 x.a01 * y.a11) % mod, (x.a10 * y.a00 x.a11 * y.a10) % mod, (x.a10 * y.a01 x.a11 * y.a11) % mod }; } Matrix pow(Matrix base, int64_t exp, int64_t mod) { Matrix res{1, 0, 0, 1}; while (exp 0) { if (exp 1) res mul(res, base, mod); base mul(base, base, mod); exp 1; } return res; } int64_t fibMatrix(int64_t n, int64_t mod) { if (n 0) throw std::invalid_argument(n must be non-negative); if (n 0) return 0; if (n 1) return 1; Matrix base{1, 1, 1, 0}; Matrix res pow(base, n - 1, mod); return res.a00; }C面试中要注意int32_t和int64_t的选择避免出现“乘法溢出但编译器不报错”的情况。如果面试官让你直接写暴力递归递归深度较大时可能会崩所以也建议用递推。C里矩阵乘法struct传值没有性能问题因为只有四个long long面试时这样写很清晰。5.3 Python实现完整示例Python版本最接近伪代码适合快速表达思路def fib(n, modNone): if n 0: raise ValueError(n must be non-negative) if n 0: return 0 if n 1: return 1 a, b 0, 1 for _ in range(2, n 1): a, b b, (a b) if mod is None else (a b) % mod return b def matrix_mul(a, b, modNone): return [ [(a[0][0]*b[0][0] a[0][1]*b[1][0]) % mod if mod else (a[0][0]*b[0][0] a[0][1]*b[1][0]), (a[0][0]*b[0][1] a[0][1]*b[1][1]) % mod if mod else (a[0][0]*b[0][1] a[0][1]*b[1][1])], [(a[1][0]*b[0][0] a[1][1]*b[1][0]) % mod if mod else (a[1][0]*b[0][0] a[1][1]*b[1][0]), (a[1][0]*b[0][1] a[1][1]*b[1][1]) % mod if mod else (a[1][0]*b[0][1]