递归算法概述及常见算法列表，传送门：
http://blog.csdn.net/nthack5730/article/details/65537530
斐波那契数列
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……
这个数列从第三项开始，每一项都等于前两项之和。
递归求斐波那契(Fibonacci)数列
在这里我将根据递归两大特点（法则）和斐波那契数列的逻辑来设计对应的递归程序
1.递归程序的定义
首先，设计一个fibo(int n)方法，返回值为：数列中第n个数的值
【注：斐波那契数第一个数值为1，第二个数值也是1，从第三个开始，每个数值为前两个数的和】
当求【n=5】时，实际上是求当【n=3】和【n=4】时的和；
那么求【n=3】就是求【n=1】和【n=2】时的和…..
以此类推….
当【n=1】或【n=2】时，程序直接返回1。
可得出公式：
f(n) = f(n-1) + f(n-2)
不难得出基本的递归调用代码：
public static int fibo(int n) {
return fibo(n - 1) + fibo(n - 2);
}
细心的人会发现这段代码是会得到递归死循环的，因为缺少了递归终止条件（跳出条件）
此文老猫原创，转载请加本文连接：http://blog.csdn.net/nthack5730/article/details/66796854
更多有关老猫的文章：http://blog.csdn.net/nthack5730
2.递归程序的终止条件
1. 当【n=1】或【n=2】时，程序直接返回1。
if( n== 1 || n ==2){
return 1;
}
2. 当然，也可以设计程序当【n=0】时返回0以及【n=1】时返回1；
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
因为【n=2】是由【n=1】和【n=0】的和得到，也是1。
可以得出最终的代码：
public static int fibo(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else{
return fibo(n - 1) + fibo(n - 2);
}
}
#
此文老猫原创，转载请加本文连接：http://blog.csdn.net/nthack5730/article/details/66796854
更多有关老猫的文章：http://blog.csdn.net/nthack5730
3. 注意跳出的边界所在
上面代码片中，第一个代码片就限制了n必须大于0，也就是n不能等于0，否则会出现“递归死循环”引发“StackOverflow”异常。
在这里就可以引出“跳出递归调用边界”这种说法，也就是终止递归调用条件的值的设定！这个值的设定是需要根据现实计算情况和要求的计算逻辑实现的。
例如：
在斐波那契数列中，设计终止递归循环的边界是可以随意的，只要符合斐波那契数列的计算逻辑：
1. 终止条件中的n的最小值要大于等于0，小于0没有任何意义，并且不符合斐波那契规则，造成不可估量错误。
2. 要包含当n为基数以及偶数两种情况下n的返回值，主要是因为递归调用时有f(n-1)和f(n-2)，那么就一定有奇偶数两种情况。
例子1：可以设计为在n=6时返回8，在n=7时返回13。
public static int fibo(int n) {
if (n == 6) {
return 8;
} else if (n == 7) {
return 13;
} else{
return fibo(n - 1) + fibo(n - 2);
}
}
例子2：可以设计为在n=6时返回8，在n=5时返回5。
public static int fibo(int n) {
if (n == 6) {
return 8;
} else if (n == 5) {
return 5;
} else{
return fibo(n - 1) + fibo(n - 2);
}
}
两个例子基本相同，就是在调用的时候有不同：
调用时传入参数n的最小值不能小于终止判断条件的最小判断值：
例子1.规定了n必须大于6
例子2.规定了n必须大于5
至于怎么选择，就在于使用者在实际中的需求来调整！
此文老猫原创，转载请加本文连接：http://blog.csdn.net/nthack5730/article/details/66796854
更多有关老猫的文章：http://blog.csdn.net/nthack5730
