思想：一个大问题，是通过子问题尝试的方式来解决的。
image.png
EG1：求n!的结果
思路：
如果用递归的思想，就把他划分为n*(n-1)!
代码
public static long getFactorial1(int n) {
if (n == 1) {
return 1L;
}
return (long) n * getFactorial1(n - 1);
}
public static long getFactorial2(int n) {
long result = 1L;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args){
int n = 6;
System.out.println(getFactorial1(n));
System.out.println(getFactorial2(n));
}
EG2：汉诺塔问题
image.png
汉诺塔问题即，一个杆子上有从上到下按照从小到大排序的圆盘，现在有三个杆子，想要把一个杆子上的圆盘移动到另一个杆子，移动过程中不允许出现大圆盘压小圆盘，可以从左杆子直接移动到右杆子这种操作
思路：
比如想把左边的圆盘全部移动到右边圆盘上，右如下过程
1.把左圆盘的n-1个移动到中圆盘
2.把做原盘的第n个移动到右圆盘
3.把中的n-1个圆盘移动到右圆盘
把过程拆分无非就是六个过程，盘子从左到右，从左到中，从中到右，从中到左，从右到中，从右到左，实现如下，只实现一个，剩下同理，互相调用即可
public static void moveLeftToRight(int n){
if (n ==1){
//即左杆子上只有一个圆盘，直接移动即可
System.out.println("move" + n +"from left to right" );
}
moveLeftToMid(n-1);
System.out.println("move" + n +"from left to right");
moveMidtoRight(n-1);
}
上面的思路是拆分到具体的过程，实现简单的方法是，把左中右三个杆子的思想去掉，把三个杆子分别看成from，to，help，from是盘子原来的杆子，to是要去的杆子，help是需要经过的中间杆子（比如n个盘子从左到右，就需要经过中间的这个help杆子实现），有了这三个杆子后，不管从哪到哪，都是from杆子到to杆子的过程，整体的过程就变成了把n-1先移动到help杆子，再把n从from杆子移动到to，在把n-1从help移动到to即可
代码：
public static void Hanoi(int n){
if (n>0){
func(n,"left","mid","right");
}
}
public static void func(int n,String from,String help,String to){
if (n==1){
System.out.println("move from" + from + "to" + to);
}else {
func(n-1,from,to,help);
func(1,from,help,to);
func(n-1,help,from,to);
}
}
注意一下这里的help杆子，只是代表他所起的一个作用，比如你在实现把n个盘子从from到to的时候，子过程需要把n-1从from到help，这一步怎么实现呢，就得把n-2个先从from移动到to，这里的to起到的作用就是help的作用。
EG3:
题目：子序列，比如{a,b,c}的子序列是a,b,c,ab,abc,bc,ac,空。必须是按顺序的才算子序列
image.png
思路：打印过程因为是按顺序的，所以可以从第一个元素开始看成一个二叉树，左分支是打印，右分支是不打印，如下图
image.png
形成这样一个二叉树后，需要打印它，思路是把二叉树看成一个数组，打印数组，打印方法：
1.如果数组下标没有移动到空即最后一个元素的下一个元素，下标就加一，直到下标为空，打印当前的，如下图
image.png
下标移动到了C后面，即空，打印abc
2.然后把c位置的数用一个临时变量存储起来，把c位置置零，然后仔打印
3.重复如上过程，即触底打印，打印后把当前i位置的数置零，再触底打印的过程
代码：
public static void printAllSubsquence(String str) {
char[] chs = str.toCharArray();
process(chs, 0);
}
public static void process(char[] chs, int i) {
if (i == chs.length) {
System.out.println(String.valueOf(chs));
return;
}
process(chs, i + 1);
char tmp = chs[i];
chs[i] = 0;
process(chs, i + 1);
chs[i] = tmp;
}
public static void main(String[] args) {
String test = "abc";
printAllSubsquence(test);
}
经观察发现，如上实现过程实际上是吧二叉树最底层所代表的累计结果从左到右打印了
要注意递归跳跃信任，就是字面的意思要相信递归跳跃是对的，对于此题，无非就是两个过程，第一个是有的话一直触底打印，然后再出没有的情况，没有的情况怎么构造呢，就是把那个位置用临时变量存储，然后置零就构造出了，这两个情况构成了所有情况。
EG4：
题目：
image.png
即比如{a,b,c} 全排列是abc,acb,bac,bca,cab,cba
思路：
还是上面说的整体的问题划分成小的问题，然后重组，这个题就可一看成，选定第一个位置，然后全排列剩下的位置，这样的递归，在实现的时候怎么实现呢，就是以第一个位置为基点，全排列后面面的，全排列后，把第一个位置的数换成后面的数，再递归就可以了。比如abc，选定a,然后全排列bc,
然后交换ab的位置，bac这个顺序，再执行第一步的过程即可。
代码：
public static void printAllPermutations1(String str) {
char[] chs = str.toCharArray();
process1(chs,0);
}
public static void process1(char[] chs, int i) {
if (i==chs.length){
System.out.println(String.valueOf(chs));
}
for (int j = i;j<chs.length;j++){
swap(chs,i,j);
process1(chs,i+1);
swap(chs,i,j);
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
EG5：
题目：
image.png
思路：
只需再例四的基础上加一个判断头位置的元素是否重复出现过，如果不重复出现再全排列，代码中用hashset来检测是否包含
代码：
public static void printAllPermutations2(String str) {
char[] chs = str.toCharArray();
process2(chs, 0);
}
public static void process2(char[] chs, int i) {
if (i==chs.length){
System.out.println(String.valueOf(chs));
}
HashSet<Character> set = new HashSet<>();
for (int j = i;j<chs.length;j++){
//这里注意，判断条件因为交换后j位置就变成了头所以，是判断是否包含j位置元素去重
if (!set.contains(chs[j])){
set.add(chs[j]);
swap(chs,i,j);
process2(chs,i+1);
swap(chs,i,j);
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
String test1 = "abc";
printAllPermutations1(test1);
System.out.println("======");
printAllPermutations2(test1);
System.out.println("======");
String test2 = "acc";
printAllPermutations1(test2);
System.out.println("======");
printAllPermutations2(test2);
System.out.println("======");
}
EG6：
题目：
image.png
思路：分析，即如果求第N年牛的数量，F（n）=F（n-1）+F（n-3）
代码：
public static int cowNumber1(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2 || n == 3) {
return n;
}
return cowNumber1(n - 1) + cowNumber1(n - 3);
}
EG7
题目：告诉你一个数字串，能转变成多少种字母串，有多少种转换方式，数字串对应1-a,2-b等
例如1111可以转变成aaaa,aka,kaa,kk，共四种解法
image.png
EG8:
题目：
image.png
思路：
构造共两个函数，一个函数是抽取栈底元素（获得并删除），另一个就是开始逆序，递归过程。
image.png
image.png
代码：
public static void reverse(Stack<Integer> stack){
if (stack.isEmpty()){
return;
}
int last = getAndRemoveLastElements(stack);
reverse(stack);
stack.push(last);
}
public static int getAndRemoveLastElements(Stack<Integer> stack){
int res = stack.pop();
if (stack.isEmpty()){
return res;
}else {
int last = getAndRemoveLastElements(stack);
stack.push(res);
return last;
}
}
public static void main(String[] args) {
Stack<Integer> test = new Stack<Integer>();
test.push(1);
test.push(2);
test.push(3);
test.push(4);
test.push(5);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
以上就是递归及其思想，主要锻炼的是递归感觉，就是怎么把一个大过程分解成小过程，在合并
网友评论