方法一：递归法

public class Solution {
    public int Fibonacci(int n) {
        if (n == 1 || n == 2) 
            return 1;
        else 
            return Fibonacci(n-1) + Fibonacci(n-2);
    }
}

对斐波那契数列进行抽象

我想通过对这个规则的抽象，来寻找对这个问题的可能的解法。

对于斐波那契数列，其规则是，从第 3 项开始，每一项的值为其前两项的和。若我对这个规则进行一定的修改，改成：从第 3 项开始，每一项的值为其前两项的差，即满足下式子：

f(n)={n,n=1,2f(n−1)−f(n−2),n>2f(n)=\left\{\begin{matrix} n, n=1,2 \\ f(n-1)-f(n-2),n>2 \end{matrix}\right.

则会得到一个数列： 1,1,0,1,-1,2,-3,5,-8,13,-21

可以看到，对于该数列，将第 4 个元素记为第一个元素，则可以看到后面的数列中，偶数项为斐波那契数列对应项的相反数。这是个有趣的规律。

对斐波那契数列规则进行抽象：

从第三个元素开始，每一个元素的表现为其前两个元素相互作用的结果。

为什么可以用递归模拟斐波那契数列？

对于斐波那契数列，各项值满足下面的表达式：

f(n)={n,n=1,2f(n−1)+f(n−2),n>2f(n)=\left\{\begin{matrix} n, n=1,2 \\ f(n-1)+f(n-2),n>2 \end{matrix}\right.

其实，观察斐波那契数列的表达式可以发现，其表达式中，就已经可以看到递归。即f(n-1)+f(n-2)这一部分。在式子中，f(n) 的含义就是第 n 项的值，那么 f(n-1) 的含义就是第 n-1 项的值，f(n-2) 以此类推，所以 f(n)=f(n-1)+f(n-2) 所表达的含义为：第 n 项的值，为其前两项的和。因为这一点，想到用递归来模拟斐波那契数列，其实是一个比较自然的想法。

因此，对于题解的方法一，其实只是翻译了一下斐波那契数列的表达式而已。