#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