1 递归的思想
以此类推是递归的基本思想。
具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。
递归的两个条件
- 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。（自身调用）
- 存在一种简单情境，可以使递归在简单情境下退出。（递归出口）
2 怎么更好地理解递归算法
递归：你打开面前这扇门，看到屋里面还有一扇门（这门可能跟前面打开的门一样大小（静），也可能门小了些（动）），你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开，。。。， 若干次之后，你打开面前一扇门，发现只有一间屋子，没有门了。 你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这钥匙开了几扇门。递归就是有去（递去）有回（归来）。
循环：你打开面前这扇门，看到屋里面还有一扇门，（这门可能跟前面打开的门一样大小（静），也可能门小了些（动）），你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，（前面门如果一样，这门也是一样，第二扇门如果相比第一扇门变小了，这扇门也比第二扇门变小了（动静如一，要么没有变化，要么同样的变化）），你继续打开这扇门，。。。，一直这样走下去。 入口处的人始终等不到你回去告诉他答案。
3 应用场景
3.1 Fibonacci数列.
提到递归，我们可能会想到的一个实例便是斐波那契数列。斐波那契数列就是如下的数列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …，
总之，就是第N(N > 2)个数等于第(N - 1)个数和(N - 2)个数的和。用递归算法实现如下：
实现代码：
package com.boer.tdf.act.demo.recursion;
/**
* Fibonacci数列.
*
* 提到递归，我们可能会想到的一个实例便是斐波那契数列。斐波那契数列就是如下的数列：
*
* 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …，
* 总之，就是第N(N > 2)个数等于第(N - 1)个数和(N - 2)个数的和。用递归算法实现如下：
*/
public class Fibonacci {
/**
* Fibonacci数列
* @param n 数的位置
* @return
*/
public static int fibonacci(int n) {
if (n < 0) return -1;
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) throws Exception {
Fibonacci fibonacci = new Fibonacci();
System.out.println(fibonacci.fibonacci(10));
/**
* 运行结果:55
*/
}
}
3.2 阶乘
还有就是求一个数的阶乘，也会用到递归，这个比较简单，直接给出实现代码：
package com.boer.tdf.act.demo.recursion;
/**
* 阶乘 .
* 还有就是求一个数的阶乘，也会用到递归，这个比较简单，直接给出实现代码
*/
public class Factorial {
public static int factorial(int n) {
int sum = 0;
if (0 == n)
return 1;
else
sum = n*factorial(n-1);
return sum;
}
public static void main(String[] args) throws Exception {
Factorial factorial = new Factorial();
System.out.println(factorial.factorial(6));
/**
* 运行结果:720
*/
}
}
在求解6的阶乘时，递归过程如下所示。
我们会惊奇的发现这个过程和栈的工作原理一致对，递归调用就是通过栈这种数据结构完成的。整个过程实际上就是一个栈的入栈和出栈问题。然而我们并不需要关心这个栈的实现，这个过程是由系统来完成的。
那么递归中的“递”就是入栈，递进；“归”就是出栈，回归。
3.3 汉诺塔问题
汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
汉诺塔是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
- 每次只能移动一个圆盘；
- 大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
下面是汉诺塔的递归求解实现：
package com.boer.tdf.act.demo.recursion;
/**
* 汉诺塔问题.
* 汉诺塔是根据一个传说形成的数学问题：
*/
public class Hanoi {
public static void hannoi(int n, String from, String buffer, String to) {
if (n == 1) {
System.out.println("Move disk " + n + " from " + from + " to " + to);
} else {
hannoi(n - 1, from, to, buffer);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hannoi(n - 1, buffer, from, to);
}
}
public static void main(String[] args) throws Exception {
Hanoi hanoi = new Hanoi();
hanoi.hannoi(4,"1","2","3");
/**
* 运行结果:
* Move disk 1 from 1 to 2
Move disk 2 from 1 to 3
Move disk 1 from 2 to 3
Move disk 3 from 1 to 2
Move disk 1 from 3 to 1
Move disk 2 from 3 to 2
Move disk 1 from 1 to 2
Move disk 4 from 1 to 3
Move disk 1 from 2 to 3
Move disk 2 from 2 to 1
Move disk 1 from 3 to 1
Move disk 3 from 2 to 3
Move disk 1 from 1 to 2
Move disk 2 from 1 to 3
Move disk 1 from 2 to 3
*/
}
}
3.4 排列组合
对于一个长度为n的串或者n个字符(数字、节点)组成的字符串数组，它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题。如1,2,3，全排列可得到：{123,132,213,231,312,321}，输出任意个数字母、数字的全排列 。
用递归算法实现代码如下：
package com.boer.tdf.act.demo.recursion;
/**
* 输出任意个数字母、数字的全排列 .
*
* 对于一个长度为n的串或者n个字符(数字、节点)组成的字符串数组，
* 它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题。
* 如1,2,3，全排列可得到：{123,132,213,231,312,321}。
*/
public class Permutation {
public static void permutation(String[] nums, int m, int n) {
String t;
if (m < n - 1) {
permutation(nums, m + 1, n);
for (int i = m + 1; i < n; i++) {
// 可抽取Swap方法
t = nums[m];
nums[m] = nums[i];
nums[i] = t;
permutation(nums, m + 1, n);
// 可抽取Swap方法
t = nums[m];
nums[m] = nums[i];
nums[i] = t;
}
} else {
for (int j = 0; j < nums.length; j++) {
System.out.print(nums[j]);
}
System.out.print(",");
}
}
public static void main(String[] args) throws Exception {
String[] str=new String[]{"1","2","3"};
Permutation permutation = new Permutation();
permutation.permutation(str,0,str.length);
/**
* 输出结果:123,132,213,231,321,312,
*/
}
}
3.5 归并排序
归并排序也是递归的典型应用，其思想：将序列分为若干有序序列（开始为单个记录），两个相邻有序的序列合并成一个有序的序列，以此类推，直到整个序列有序。
归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。
工作原理：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤3直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
代码实现：
package com.boer.tdf.act.demo.recursion;
/**
* 归并排序.
*/
public class MergeSort {
static int number=0;
public static void main(String[] args) {
int[] a = {14, 12, 15, 13, 11, 16 };
printArray("排序前：",a);
MergeSort(a);
printArray("排序后：",a);
}
private static void printArray(String pre,int[] a) {
System.out.print(pre+"\n");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+"\t");
System.out.println();
}
private static void MergeSort(int[] a) {
System.out.println("开始排序");
Sort(a, 0, a.length - 1);
}
private static void Sort(int[] a, int left, int right) {
if(left>=right)
return;
int mid = (left + right) / 2;
// 二路归并排序里面有两个Sort，多路归并排序里面写多个Sort就可以了
Sort(a, left, mid);
Sort(a, mid + 1, right);
merge(a, left, mid, right);
}
private static void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];
int r1 = mid + 1;
int tIndex = left;
int cIndex=left;
// 逐个归并
while(left <=mid && r1 <= right) {
if (a[left] <= a[r1])
tmp[tIndex++] = a[left++];
else
tmp[tIndex++] = a[r1++];
}
// 将左边剩余的归并
while (left <=mid) {
tmp[tIndex++] = a[left++];
}
// 将右边剩余的归并
while ( r1 <= right ) {
tmp[tIndex++] = a[r1++];
}
System.out.println("第"+(++number)+"趟排序:\t");
// 从临时数组拷贝到原数组
while(cIndex<=right){
a[cIndex]=tmp[cIndex];
// 输出中间归并排序结果
System.out.print(a[cIndex]+"\t");
cIndex++;
}
System.out.println();
}
}
3.6 趣味问题——年龄。
有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？用递归算法实现。
package com.boer.tdf.act.demo.recursion;
/**
* 趣味问题——年龄。
*
* 有5个人坐在一起，
* 问第五个人多少岁？他说比第4个人大2岁。
* 问第4个人岁数，他说比第3个人大2岁。
* 问第三个人，又说比第2人大两岁。
* 问第2个人，说比第一个人大两岁。
* 最后问第一个人，他说是10岁。
*
* 请问第五个人多大？用递归算法实现。.
*/
public class Recursion01 {
/**
* 用循环计算这道题
* @param num 人数
* @return
*/
public static int getAge01(int num) {
int age = 10;
while (num>1) {
age += 2;
num -= 1;
}
return age;
}
/**
* 换成递归计算这道题
* @param num 人数
* @return
*/
public static int getAge02(int num) {
if (num==1) return 10;
return getAge02(num-1)+2;
}
/**
* 换成尾递归
* @param num 人数
* @param acc 岁数
* @return
*/
public static int getAge03(int num,int acc) {
if (num == 1)
return acc;
return getAge03(num-1,acc+2);
}
public static void main(String[] args) throws Exception {
Recursion01 recursion01 = new Recursion01();
System.out.println(recursion01.getAge01(5));
System.out.println(recursion01.getAge02(5));
System.out.println(recursion01.getAge03(5,10));
/**
* 运行结果:
* 18
18
18
*/
}
}
