四.递归

递归算法可以缩小规模。递归方法调用自身，但是参数不一样。递归可以用循环或者栈来代替

1.递归的两个要素：边界条件，递归表达式

2.递归算法的时间复杂度

（1）递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归的时间复杂度

　　递归次数和递归深度有关，递归次数就是二叉树的节点个数

（2）很多时候，递归可以抽象成一棵二叉树，时间复杂度和二叉树的节点个数有关（递归的次数就是节点的个数）

　　满二叉树节点个数：2ⁿ-1（n代表层数）第i有：2^i-1个节点

（3）不要一看到递归就想到O(logn)

3.递归算法的空间复杂度

（1）递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度

（2）空间复杂度与递归的深度有关：递归深度就是调用栈的深度，就是二叉树的深度

1.二分查找

（1）非递归实现

 1     public static int binarySerach(int[] arr,int key) {
 2         int left=0;
 3         int right=arr.length-1;
 4         
 5         while(left<=right) {
 6             int mid=(left+right)/2;
 7             if(key==arr[mid])
 8                 return mid;
 9             if(key<arr[mid])
10                 right=mid-1;
11             if(key>arr[mid]) 
12                 left=mid+1;
13         }
14         return -1;
15     }

View Code

（2）递归实现

 1     public static int binarySerach(int[] arr,int key,int left,int right) {
 2         int mid=(left+right)/2;
 3         
 4         if(left>right)
 5             return -1;
 6         if(key==arr[mid])
 7             return mid;
 8         
 9         if(key<arr[mid])
10             return binarySerach(arr, key, left, mid-1);
11         
12         if(key>arr[mid])
13             return binarySerach(arr, key, mid+1, right);
14         return -1;
15 
16     }

View Code

2.汉诺塔问题

1     public static void move(int dish,String from,String temp,String to) {
2         if(dish==1)
3             System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to);
4         else {
5             move(dish-1, from, to, temp);////A为初始塔座，B为目标塔座，C为中介塔座
6             System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to);
7             move(dish-1, temp, from, to);//B为初始塔座，C为目标塔座，A为中介塔座
8         }
9     }

View Code

3.归并排序

4.消除递归

5.递归的有趣应用

（1）求一个数的乘方

（2）背包问题

（3）组合：选择一支队伍