递归介绍
递归在程序语言中简单的理解是：方法自己调用自己。
递归其实和循环是非常像的，循环都可以改写成递归，递归未必能改写成循环，这是一个充分不必要的条件。
- 那么，有了循环，为什么还要用递归呢？？在某些情况下(费波纳切数列，汉诺塔)，使用递归会比循环简单很多很多
想要用递归必须知道两个条件：
- 递归出口(终止递归的条件)
- 递归表达式(规律)
技巧：在递归中常常是将问题切割成两个部分(1和整体的思想)，这能够让我们快速找到递归表达式(规律)
求和
如果我们使用for循环来进行求和1+2+3+4+….+100，那是很简单的：
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum = sum + i;
}
System.out.println("公众号：Java3y：" + sum);
for循环都可以使用递归来进行改写，而使用递归必须要知道两个条件：
- 递归出口
- 递归表达式(规律)
我们来找出它的规律：1+2+3+…+n，这是一个求和的运算，那么我们可以假设X=1+2+3+…+n，可以将1+2+3+…+(n-1)看成是一个整体。而这个整体做的事又和我们的初始目的(求和)相同。以我们的高中数学知识我们又可以将上面的式子看成X=sum(n-1)+n
我们找到我们的递归表达式(规律)，它就是sum(n-1)+n,那递归出口呢，这个题目的递归出口就有很多了，我列举一下：
如果n=1时，那么就返回1
如果n=2时，那么就返回(1+2)=3
如果n=3时，那么就返回(1+2+3)=6
递归表达式和递归出口我们都找到了，下面就代码演示：
递归出口为1：
public static void main(String[] args) {
System.out.println(sum(100));
}
/**
*
* @param n 要加到的数字，比如题目的100
* @return
*/
public static int sum(int n) {
if (n == 1) {
return 1;
} else {
return sum(n - 1) + n;
}
}
数组内部的最大值
使用的是循环，那么我们通常这样实现：
int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};
//将数组的第一个假设是最大值
int max = arrays[0];
for (int i = 1; i < arrays.length; i++) {
if (arrays[i] > max) {
max = arrays[i];
}
}
System.out.println(max);
如果我们用递归的话，那怎么用弄呢？首先还是先要找到递归表达式(规律)和递归出口
- 我们又可以运用1和整体的思想来找到规律
- 将数组第一个数->2与数组后面的数->{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}进行切割，将数组后面的数看成是一个整体X={3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}，那么我们就可以看成是第一个数和一个整体进行比较if(2>X) return 2 else(2<X) return X
- 而我们要做的就是找出这个整体的最大值与2进行比较。找出整体的最大值又是和我们的初始目的(找出最大值)是一样的
- 也就可以写成if( 2>findMax() )return 2 else return findMax()
- 递归出口，如果数组只有1个元素时，那么这个数组最大值就是它了。
使用到数组的时候，我们通常为数组设定左边界和右边界，这样比较好地进行切割。
- L表示左边界，往往表示的是数组第一个元素，也就会赋值为0(角标为0是数组的第一个元素)
- R表示右边界，往往表示的是数组的长度，也就会赋值为arrays.length-1（长度-1在角标中才是代表最后一个元素)
那么我们递归的写法就是：
public static void main(String[] args) {
int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};
System.out.println(findMax(arrays, 0, arrays.length - 1));
}
/**
* 递归，找出数组最大的值
* @param arrays 数组
* @param L 左边界，第一个数
* @param R 右边界，数组的长度
* @return
*/
public static int findMax(int[] arrays, int L, int R) {
//如果该数组只有一个数，那么最大的就是该数组第一个值了
if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整体的最大值
if (a > b) {
return a;
} else {
return b;
}
}
}
斐波那契数列
菲波那切数列长这个样子：{1 1 2 3 5 8 13 21 34 55….. n }
数学好的同学可能很容易就找到规律了：前两项之和等于第三项
如果让我们求出第n项是多少，那么我们就可以很简单写出对应的递归表达式了：Z = (n-2) + (n-1)
递归出口在本题目是需要有两个的，因为它是前两项加起来才得出第三项的值
同样地，那么我们的递归出口可以写成这样：
if(n==1) retrun 1;
if(n==2) return 2;
看一下完整的代码:
public static void main(String[] args) {
int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
//bubbleSort(arrays, 0, arrays.length - 1);
int fibonacci = fibonacci(10);
System.out.println(fibonacci);
}
public static int fibonacci(int n) {
if (n == 1) {
return 1;
} else if (n == 2) {
return 1;
} else {
return (fibonacci(n - 1) + fibonacci(n - 2));
}
}
总结
要使用递归首先要知道两件事：
- 递归出口(终止递归的条件)
- 递归表达式(规律)