#J0019. 数列回溯
数列回溯
数列回溯——递归求斐波那契数列
📖知识点详细讲解
斐波那契数列规则:前两项数字都是1,从第3项开始,每一项等于前面两项数字相加。 数列:1,1,2,3,5,8,13 …
数学关系式:
- 基线条件:第1项
f(1)=1,第2项f(2)=1,遇到1、2直接返回数值1,递归到此停下。 - 递推关系:
f(n)=f(n‑1)+f(n‑2)
求第n项的值,可以拆成求第n‑1项与n‑2项两个更小的子问题。
递归的执行过程:求f(5),需要先算出f(4)和f(3);算f(4)又需要f(3)、f(2),不断拆解,直到碰到基线条件,再把数值逐层返回回来。
题目
求出斐波那契数列第n项的值。
输入样例
2
1