递归算法
递归算法是把问题转化为规模缩小了的同类问题的子问题。然后 递归调用函数（或过程）来表示问题的解。
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
算法应用
(1)二分法搜索
是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半
/**
*二分法查找
*/
public class BinarySearch{
public static void main(String[] args){
//定义数组
int[] array={1,3,4,7,10,18,34,37,57,79,88};
//输出下标
System.out.println(search(array,0,0,array.length));
System.out.println(search(array,7,0,array.length));
System.out.println(search(array,88,0,array.length));
}
/**
*二分查找函数
*array 数组
*num 要查找的数字
*left 左边界下标
*right 右边界下标
*return 数字所在下标
*/
public static int search(int[] array,int num,int left,int right){
//寻找区间中间下标
int middle=(left+right)/2;
//如果区间成立
if(left<right){
//如果该中间下标值小于数值
if(array[middle]<num){
//递归搜索中间下标至右边界区间
return search(array,num,middle+1,right);
}
//如果该中间下标值大于数值
else if(array[middle]>num){
//递归搜索左边界至中间下标区间
return search(array,num,left,middle);
}
//如果该中间下标值等于数值返回中间值
else {
//返回中间值
return middle;
}
}
//如果区间不成立则说明找不到，返回-1
return -1;
}
}
（2）最大公约数（欧几里得辗转相除法）
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
最大公约数=m%n,再以n为m继续m%n
使用递归思想
/**
* 欧几里得最大公约数
* @author Naah
*
*/
public class GCD {
public static void main(String[] args) {
System.out.println(gcd(24, 4));
}
/**
* 最大公约数算法
* @param m 第一个数
* @param n 第二个数
* @return 最大公约数
*
* 欧几里得最大公约数为：最大公约数=m%n,再以n为m继续m%n
*/
public static int gcd(int m,int n)
{
if (n==0) {
return m;
}
else {
return gcd(n, m%n);
}
}
}
(3)汉诺塔问题
有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，
首先我们肯定是把上面n-1个盘子移动到柱子C上，然后把最大的一块放在B上，最后把C上的所有盘子移动到B上，由此我们以此为思路，写出算法：
/**
* 汉诺塔算法
* @author Naah
*
*/
public class HanNota {
static int num=1;
public static void main(String[] args) {
// TODO Auto-generated method stub
hanNota(3, 'A','B', 'C');
}
/**
*
* @param n 盘子数
* @param from 起点棍子的名称
* @param depence 依赖棍子的名称
* @param to 终点棍子的名称
*/
public static void hanNota(int n,char from,char depence,char to)
{
//如果盘子只有一个，直接输出
if (n==1) {
System.out.println(num+++"次"+":"+n+"盘子:"+from+"-->"+to);
}
else {
//将起点棍子上盘子的第一个，从起点棍子以终点棍子为依赖，挪到依赖棍子上
hanNota(n-1, from, to, depence);
//输出当前行为
System.out.println(num+++"次"+":"+n+"盘子:"+from+"-->"+to);
//将依赖棍子上的盘子的第一个，从依赖棍子以起点棍子为依赖，挪到终点棍子上
hanNota(n-1, depence, from, to);
}
}
}
（4）阶层求解法
一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1
public class jiecheng {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(jc(10L));
}
public static long jc(long n) {
if (n==0) {
return n;
}
else {
return n*jc(n-1);
}
}
}
