递归

1.递归是什么？

定义:程序调用自身的编程技巧称为递归。
递归使用的是选择结构，对于解决同样问题的孪生兄弟:迭代，它使用的则是循环结构。

2.递归的核心

先看一个例子，表达式1+2+3....+100=?要怎么写程序来计算？
第一反应是for循环：

int sum =0;
for (int i = 1; i <= 100; i++) {
sum+=i;
}
System.out.println(sum);//5050

更简洁的写法

int start =1;
int end = 100;
int sum =(start+end)*end/2;//首项加末项乘以项数除以二
System.out.println(sum);//5050

递归的写法

static int recursion(int n){
if(n==1){//递归出口
return 1;
}else{
return n+recursion(n-1);
}
}

递归的核心其实就是一个if...else... 一个条件跳出，一个条件继续。

1.优点:使程序结构更清晰,更简洁,更容易让人理解,
2.缺点:使用递归调用时，**如果过多的调用容易造成java.lang.StackOverflowError即栈溢出和程序执行过慢。这是一个潜在Bug和影响程序执行效率问题，需要谨慎使用。**对于互联网这种以速度和效率来维护用户量，不得以用递归时，可以把处理的数据放入缓存，或者直接使用迭代等方式来解决。
3.规律：递归要有出口，不然成了死循环。解出递归的要点在于求出n-1，求出了n-1才能求解出n,这是为什么呢?

3.例题

3.1.题目:有一对兔子，从出生后第3个月起每个月都生一对兔子， 小兔子长到第四个月后每个月又生一对兔子， 假如兔子都不死，问每个月的兔子总数为多少?

分析，这个题目是著名的斐波那契数列:1,1,2,3,5,8,13,21....=Sn = Sn-1+Sn-2
规律是：从第三个数开始,每个数都是前两个数的和。

迭代方式

int month =10;
int sum[]= new int[month] ; //初始化月份数组
sum[0] = 1; //第一个月
sum[1] = 1; //第二个月
for(int i=2;i<=month-1;i++){
sum[i] = sum[i-1]+sum[i-2]; //第三个月等于前两个月之和
}
System.out.println("第"+month+"个月的兔子总数是："+sum[month-1]);

递归方式

static int recursion(int i){
if( i == 1 || i == 2 ){
return 1;
}
else{
return recursion(i-1) + recursion(i-2);//第三项等于后两项之和
}
}

3.2 题目: 逆序排列字符单词,输入：I love java-->java love I

迭代方式

static String reverse(String str){
String[] strs = str.split(" ");
StringBuilder sb = new StringBuilder();
//倒叙遍历并拼接空格
for (int i = strs.length-1; i >= 0; i--) {
sb.append(strs[i]+" ");
}
return sb.toString();
}

递归方式

static String reverse(String s) {
int i = s.indexOf(" ");//搜索第一次出现" "的位置
if (s == null||i == -1) {
return s;
}
return reverse(s.substring(i + 1)) + " " + s.substring(0, i);//每次截取第一个单词放在最后拼接
}

3.3.题目:使用递归来统计字符串String str="hello"的长度,不能使用统计变量(只能用递归求解).

static int test1(String str){
if(null==str||str.equals("")){
return 0;
}
String[] strs = str.split("");
StringBuffer sb = new StringBuffer();//每次截取最后一个字母
for(int i = 0; i <= strs.length-2; i++)
{
sb. append(strs[i]);
}
return test1(sb.toString())+1;//每次递归调用+1
}

3.4 题目:实现二分查找算法.

二分查找,不断将数组进行对半分割，每次拿中间元素和goal进行比较(前提是数组元素的排序应该是递增或者递减)

public static void main(String[] args) {
int [] arr={1,2,5,6,8,9,12,64,78,90};//有序数组
System.out.println(test(arr,0,arr.length-1,8));//传入数组和数组长度,最后一个是要查找的值
}
//递归方式实现
public static int recursion(int [] arr,int low,int high,int value){
if(low>high){
return -1;
}
int mid=(low+high)/2;//求中间的值
if(value==arr[mid]){//如果相等,则找到该值,直接返回
return mid;
}else if(value<arr[mid]){//如果要找的值在中间值得左边,则下一次递归开始的右指针指向该次中间值-1
return recursion(arr,low,mid-1,value);
}else{////如果要找的值在中间值得右边,则下一次递归开始的左指针指向该次中间值+1
return recursion(arr,mid+1,high,value);
}
}
//循环方式实现
public static int test(int [] arr,int low,int high,int value){
int mid;
while(high>=low){
mid=(low+high)/2;
if(value<arr[mid]){
high=mid-1;
}else if(value>arr[mid]){
low=mid+1;
}else{
return mid;
}
}
return -1;//都没找到,则返回-1
}

3.5题目:求最大公约数和最小公倍数:

public static void main(String[] args) {
int x = 100;
int y = 18;
System.out.println("最大公约数:"+gcd(x,y));
System.out.println("最小公倍数:"+lcm(x,y));
}
//辗转相除法实现最大公约数
public static int gcd(int x, int y) {
if (y == 0){
return x;
}else{
return gcd(y, x % y);//x%y时,如果x<y则返回x,例:4%20=4 5%20=5,迭代之后会把小数放在后面,所以不用做交换
}
}
//最小公倍数　
public static int lcm(int p,int q){
int pq = p * q;
return pq / gcd(p,q);
}

3.6.题目:杨辉三角

        1 
       1 1 
      1 2 1 
     1 3 3 1 
    1 4 6 4 1 
   1 5 10 10 5 1 
 1 6 15 20 15 6 1 

分析:杨辉三角最本质的特征是，它的两条斜边都是由数字1组成的，而其余的数则是等于它肩上的两个数之和。

public static void main(String[] args) {
int n = 7;
for (int i = 1; i <= n; i++) {
//双层for循环是为了打印出三角形
for (int j = 1; j <= n-i; j++) {//每行前面的空格数
System.out.print(" ");
}
for (int j = 1; j <= i; j++) {
System.out.print(num(i,j)+" ");
}
System.out.println();//换行
}
}
public static int num(int x,int y){
if(y==1||y==x){
return 1;
}
return num(x-1,y-1)+num(x-1,y);//每一个数等于肩上两个数之和
}

3.7.题目:汉诺塔

接下来就到了递归的经典案例汉诺塔问题，本文就不对汉诺塔游戏规则进行讲解，如果以前没接触过汉诺塔，建议先玩玩汉诺塔游戏，总结一下游戏规律。

现在要把X柱上所有圆盘移动到Z
当移动3个圆盘

当移动6个圆盘

所以可以推出,当n个从x柱，经由y柱中转，移动到z柱(解出n层汉诺塔时)，有:
当n=0时，
不用做任何操作
当n>0时，
首先,将n-1个盘子从x借助z移动到y
然后,将1个盘子从x移动到z
最后,将在中间y上的n-1个盘子借助x移动到z
为了解出n层汉诺塔，需要先使用n-1层汉诺塔的解法。

static int t=0;//最少移动次数
public static void main(String[] args) {
  hanio(3,"x","y","z");
  System.out.println(t);
}
static void hanio(int n ,String src,String mid,String dest){
  if(n==1){
    System.out.println(src+"-->"+dest);//移动过程
    t++;
  }else{
    hanio(n-1,src,dest,mid);//将n-1个盘子从x借助z移动到y
    hanio(1,src,"",dest);//因为中间柱子没用到,所以可以填""或者填mid,然后将最大的盘子从x直接移动到z
    hanio(n-1,mid,src,dest);//将在中间y柱上的n-1个盘子借助x移动到z
  }
}