递归什么的其实很简单

说起递归，大家都觉得很高大上，很神秘的东西，是计算机的精髓之一。其实我们从小就听过一个耳熟能详的递归故事：从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”中国文化果然博大精深，一个小故事里蕴含了如此深奥的秘密。（这不是复读机么。。。

我们俩来做一个游戏。第一个人先从1和2中选择一个数字，第二个人可以选择加1或者加2，然后第一个人再选择加1或者加2。就这样双方交替地选择加1或者加2，谁要是正好加到10，谁就赢了。用什么策略保证一定能赢？

假如我让你先选，你选了2。接下来我选择加2，这样我加到了4，然后你选择加1，你加到了5，这时我还会选择加2，就加到了7。接下来，不论你选择加1到8，还是加2到9，我都能加到10，因此我赢定了。当然，你可能觉得先作选择的人吃亏，那么这次我先来。我选择1，你可能会选择加2到3，然后我选择加1到4。接下来，假如你选择加2到6，我会选择加1到7，这又回到第一次最后的状态了，我还是赢了。

给你5秒钟，你能不能看穿赢的关键点在哪里？1秒,2秒,3秒,4秒,5秒。。。好了，你肯定还没看出来

有人说逆向思维很重要，看问题从不同的角度，可能看到不一样的风景哦。这道题就是要反着看，我要保证我能加到10，我必须先保证我能先加到7，因为如果我先加到7，不管你加1（结果是8），还是加2（结果是9），我都能选择加1或者加2刚好结果是10。同理我要保证我能加到7，必须保证我能先加到4，所以能不能先抢到4就是胜利的关键点，如果我能抢到4，我就肯定能赢了。

如果是抢20呢？同理，倒推过去，必须要抢到17,14,11,8,5,2，所以你抢到2你就赢了。这就是计算机递归的思维，我只关心眼下的条件，只要当前的条件满足了，我就能推导出正确的结果，真的是又傻又聪明。

看一个经典的递归例子，计算斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21。。。第一个和第二个数是1从第三个数开始，它的值是前2个数之和。现在我问你第10个数是多少，你就会从第一个数开始算，1+1=2,1+2=3,2+3=5。。。如果算第20个数的值呢，我擦。。。

那按照计算机的思维该怎么算呢？很简单，我要算f(20)的值，我只要算f(19) + f(18)的值就行了，f(19)的值就是f(18) + f(17)，以此类推f(18)=f(17) + f(16)。到最后如果是第一个数f(1)那么值就是1,第二个数f(2) 那么值也是1。然后把所有的结果累加起来就得到最终的结果。

代码如下：

       public static void main(String[] args) {
 System.out.println(fib(20));
 }
 public static int fib(int n){
 if(n == 1 || n == 2){
 return 1;
 }
 return fib(n-1) + fib(n-2);
 }

是不是超级简洁，很有美感，递归我也会了！果然验证了真理往往是简单的这句名言。