要理解递归，先得理解递归
对于一个整天写增删改查的java程序员，厌倦了成天搬砖，所以最近研究了一下递归。首先声明，本人非科班出身，对于刚接触递归就感觉有一种莫名高大上算法的赶脚，本着好奇+梦想成为牛逼攻城狮的想法，就来探一探递归算法的究竟。
1.递归是什么?
定义:程序调用自身的编程技巧称为递归。它分为调用阶段和回退阶段，递归的回退顺序是它调用顺序的逆序。递归使用的是选择结构，对于解决同样问题的孪生兄弟:迭代，它使用的则是循环结构。
为了加深理解递归，可以多点点该链接:递归.(出口就是右上角x)
接下来，我们思考一个问题：表达式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);
}
}通过初体验对比,不难发现以下递归有以下几个要点:
1.优点:使程序结构更清晰,更简洁,更容易让人理解,
2.缺点:使用递归调用时，如果过多的调用容易造成java.lang.StackOverflowError即栈溢出和程序执行过慢。这是一个潜在Bug和影响程序执行效率问题，需要谨慎使用。对于互联网这种以速度和效率来维护用户量，不得以用递归时，可以把处理的数据放入缓存，或者直接使用迭代等方式来解决。
3.规律：递归要有出口，不然成了死循环。解出递归的要点在于求出n-1，求出了n-1才能求解出n,这是为什么呢?
2.递归的执行过程:
为了搞清楚递归的执行过程，我们配合实例来讲解。在求解阶乘n!=n*(n-1)*(n-2)...*3*2*1时，我们可以写出数学表达式：
从表达式中可以明显的可以看出：1.递归有出口。2.递归是选择结构。
static int factorial(int n){
if(n==0){
return 1;
}else{
return n*factorial(n-1);
}
}它的调用顺序是怎么样的呢
或者这样:
调用阶段
回退阶段
图中红色箭头为调用阶段，绿色箭头为回退阶段。解出递归的要点在于求出n-1,求出了n-1才能求解出n，它思想其实和数学中的归纳本质上是相同的。大家现在是不是可以理解递归回退顺序是它调用顺序的逆序了呢？博主精选了几道题目来加深理解递归:
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);//第三项等于后两项之和
}
}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.题目:使用递归来统计字符串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
}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
}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);
} 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);//每一个数等于肩上两个数之和
}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层汉诺塔的解法。
从推到过程中我们可以发现：解出递归的要点在于求出n-1，求出了n-1才能求解出n。此外，从数学角度也可以归纳出0,1,3,7,15,63...表达式为:f(n)=2^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
}
}4.总结和展望
文章开始简单的题目还可以用迭代来求解，随着题目的难度增加，递归对于解决某些问题非常方便，也易于理解。虽然用迭代不是不可以实现，只是同样为了解决某些特性问题，写出迭代的代码花费的时间和难度却比递归高。前文提到，递归和数学中的归纳思想本质上是相同的，都是"将复杂的问题简化"。掌握递归思想的核心就在于"把握结构",因为把握结构是分解整个问题的突破口。
本文有写的不当之处,还望大家指出.或者有其他解法,欢迎评论区分享交流
腾讯云开发者
