08《算法入门教程》递归算法之斐波那契数列

1. 前言

本节内容是递归算法系列之一：斐波那契数列递归求解，紧张先容了斐波那契数列的界说，然后用递归的实现思想分析了一下斐波那契数列，最后给出了基于 Java 代码应用递归思想实现斐波那契数列的代码实现及简朴讲授。
2. 什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），也称之为黄金分割数列，由意大利数学家列昂纳多・斐波那契（Leonardo Fibonacci）提出。斐波那契数列指的是如许的一个数列：1、1、2、3、5、8、13、21、34、……，这个数列从第 3 项开始，每一项都即是前面两项之和。在数学上，斐波那契数列可以被递推的方法界说如下：

F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

斐波那契数列是数学上面一个经典的例子，而且在一样平常生活中有许多应用，他还与黄金分割有着密不可分的接洽，而且当 n 趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割值 0.618。
3. 用递归方法求解斐波那契数列

在这一节中，我们就必要使用递归的思想去求解斐波那契数列，当给出一个斐波那契中第几项的数字，然后求解出对应的斐波那契数值。在之前，我们已经界说了递归算法的干系概念，而且明白了必要应用递归时间的三要素：

• 递归停止条件；
  
• 递归停止时间的处置惩罚方法；
  
• 递归中重复的逻辑提取，缩小题目规模。
  

接下来，我们将使用递归的知识来办理斐波那契数列题目，明白在斐波那契数列求解题目中的递归三要素分别是什么。

斐波那契数列的递归停止条件
显然易见，通过观察斐波那契数列的界说，我们很轻易发现当 n=1 大概 n=2 时，是斐波那契数列的递归停止条件，这个时间可以给出斐波那契数列的详细值。

斐波那契数列递归停止时间的处置惩罚方法
同样的，基于斐波那契数列的递推界说，当斐波那契数列到达停止条件 n=1 大概 n=2 时，我们也很轻易发现对应 F(1)=1，F(2)=1，这就是斐波那契数列在递归停止时对应的取值。

斐波那契数列的递归重复逻辑提取
按照斐波那契数列的数学界说，F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*），即当 n ≥ 3 时，斐波那契数列中这一项的值即是前面两项的值之和，如许便可以将求解一个比力大的斐波那契数列转化为求解较小数值的斐波那契数列值，这内里有重复逻辑可以递归复用。

比方，当我们求解斐波那契数列中的 F(5) 时，按照界说，我们有：

F(5) = F(4) + F(3) // 递归分解
= ( F(3) + F(2) ) + ( F(2）+F(1) ) // 递归求解
= [ ( F(2)+F(1) ) + 1 ] + ( 1+1 ) // 递归求解，碰到停止条件就求解
= [(1+1) +1 ]+(1+1) // 归并
= 3 + 2 // 归并
= 5 // 归并

4. 基于 Java 代码示例及实现讲授

在分析斐波那契数列的递归形貌之后，我们看看怎样用 Java 代码来实现对斐波那契数列的盘算。