递归算法
在函数或子过程的内部，直接或者间接地调用自己的算法。
特点：(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在 递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成 栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。(回溯)
(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)
递归设计经验：找重复(子问题)
找重复中的变化量–>参数
找参数变化趋势 –> 设计出口
解递归的常见思路：切蛋糕思维，如求阶乘f(n) = n * f(n-1)，数组就和，翻转字符串。
化不开的，看有没有递推公式？有没有等价转化？ 如：斐波那契数列f(n) = f(n-1) + f(n-2)，求最大公约数:f(m,n) = f(n, m%n)。
递归算法C语言实例
利用递归实现1到100以内的求和；1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16#include
int main()
{
int Sum(int n);
printf("sum=%d\n",Sum(100));
return 0;
}
int Sum(int n)
{
int n,sum=0;
if(n==0)
return 0;
else
return sum=n+Sum(n-1);
}
利用递归求阶乘：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#include
int main()
{
int Fac(int n);
printf("f=%d\n",Fac(5));
return 0;
}
int Fac(int n)
{
int f=0;
if(n==1)
return f=1;
else
return f=n*Fac(n-1);
}
利用递归求数组中最大数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#include
int main()
{
int Max(int a[],int n);
int a[5]={4,75,23,300,53};
printf("最大数是%d\n",Max(a,5));
return 0;
}
int Max(int a[],int n)
{
if(n==1)
return a[0];
else
{
if(a[n-1]>Max(a,n-1))
return a[n-1];
else
return Max(a,n-1);
}
}
递归算法java语言实例：
斐波那契序列：斐波那契数列问题，等价于两个子问题：
求前一项
求前两项
两项求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14public class 斐波那契序列{
public static void main(String[] args){
for(int i = 1; i < 10; i++) {
System.out.print(fibonacci(i) + " ");
}
}
public static int fibonacci(int n){
if(n == 1 || n == 2)
return 1;
return fibonacci(n-1) + fibonacci(n-2);
}
}
运行结果:
11 1 2 3 5 8 13 21 34
最大公约数：1
2
3
4
5
6
7
8
9public class 最大公约数{
public static void main(String[] args){
System.out.println(gcd(24,30));
}
public static int gcd(int m, int n){
if(n == 0) return m;
return gcd(n, m%n);
}
}
程序运行结果：
16
插入排序改递归：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public class 递归_插入排序{
public static void main(String[] args){
int[] arr = {9, 18, 2, 3, 6 ,4, 0};
insertSort(arr, arr.length-1);
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
// 对数组0-倒数第一个排序
// 等价于：
// 对数组0-倒数第二个元素排序，
//然后把最后一个元素插入到这个有序的部分中
public static void insertSort(int[] arr, int k){
if(k == 0)
return;
//对前k-1个元素排序
insertSort(arr, k-1);
//把位置k的元素插入到前面的部分
int x = arr[k];
int index = k-1;
while(index >= 0 && x < arr[index]) {
arr[index+1] = arr[index];
index--;
}
arr[index+1] = x;
}
}
程序运行结果：
10 2 3 4 6 9 18
汉诺塔问题：将1-N从A移动到B，C作为辅助。等价于：
1~N-1移动到C，A作为源，B作为辅助
把N从A移动到B
把1~N-1 从C移动到B,A为辅助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public class 汉诺塔{
public static void main(String[] args){
printHanoiTower(3, "A", "B", "C");
}
/**
* 将1-N从A移动到B，C作为辅助。等价于：
*1. 1~N-1移动到C，A作为源，B作为辅助
*2. 把N从A移动到B
*3. 把1~N-1 从C移动到B,A为辅助
* @param N N个盘子
* @param from 放盘子的初始柱子
* @param to 目标柱子
* @param help 辅助柱子
*/
public static void printHanoiTower(int N, String from, String to, String help){
if(N == 1) {
System.out.println(N + ": " + from + "-->" + to);
return;
}
// 先把前N-1个盘子挪到辅助空间上去
printHanoiTower(N-1, from, help, to);
// N可以顺利到达目标
System.out.println(N + ": " + from + "-->" + to);
// 让N-1个盘子从辅助空间回到"原位置上"
printHanoiTower(N-1, help, to, from);
}
}
程序运行结果：
1
2
3
4
51: A-->B
2: A-->C
1: B-->C
3: A-->B
1: C-->A
二分查找递归解法：全范围二分查找，等价于三个子问题：
左边找(递归)
中间比
右边找(递归)
注意：左边查找和右边查找只选其一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public class 递归_二分查找{
public static void main(String[] args){
int[] arr = {1, 3, 9, 13, 19, 23, 25};
System.out.println(binarySearch(arr, 0, arr.length-1, 13));
}
public static int binarySearch(int[] arr, int low, int high, int key){
if(low > high)
return -1;
int mid = low + ((high-low)>>1);//(low+high)>>1
int midVal = arr[mid];
if(midVal < key) //向左找
return binarySearch(arr, mid + 1, high, key);
else if(midVal > key) //向右找
return binarySearch(arr, low, mid - 1, key);
else
return mid; //key found
}
}
程序运行结果：
13
递归算法的性能分析：
斐波那契数列递归实现改进：通过记录每次f(n)的值来防止大量重复计算，大大增加了性能。
1
2
3
4
5
6
7
8
9
10public static int fib(int n, int[] tmp){
if(tmp[n] != 0) {
return tmp[n];
}
if(n == 1 || n == 2)
return 1;
tmp[n] = fib(n-1, tmp) + fib(n-2, tmp);
return fib(n-1, tmp) + fib(n-2, tmp);
}
改进前和改进后性能对比：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38public class 斐波那契序列{
static int count = 0;
static int count1 = 0;
public static void main(String[] args){
for(int i = 1; i < 20; i++) {
System.out.print(fibonacci(i) + " ");
}
System.out.println();
System.out.println("运算次数：" + count);
int[] tmp = new int[20];
for(int i = 1; i < 20; i++) {
System.out.print(fib(i, tmp) + " ");
}
System.out.println();
System.out.println("运算次数：" + count1);
}
public static int fibonacci(int n){
if(n == 1 || n == 2)
return 1;
count++;
//System.out.print("") ;
return fibonacci(n-1) + fibonacci(n-2);
}
public static int fib(int n, int[] tmp){
if(tmp[n] != 0) {
return tmp[n];
}
if(n == 1 || n == 2)
return 1;
tmp[n] = fib(n-1, tmp) + fib(n-2, tmp);
//System.out.print("");
count1++;
return fib(n-1, tmp) + fib(n-2, tmp);
}
}
程序运行结果：
1
2
3
41 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
运算次数：10926
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
运算次数：17
小白上楼梯：小白正在上楼梯，楼梯有n阶台阶，小白一次可以上1阶，2阶或者3阶，实现一个方法，计算小白有多少种走完楼梯的方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39public class 小白上楼梯{
public static void main(String[] args){
long now = System.currentTimeMillis();
for(int i = 1; i < 30; i++) {
int[] tmp = new int[1000];
System.out.print(f(i, tmp)+ " ");
}
System.out.println();
long end = System.currentTimeMillis();
System.out.println(end-now + "ms");
long now1 = System.currentTimeMillis();
for(int i = 1; i < 30; i++) {
System.out.print(f1(i) + " ");
}
System.out.println();
long end1= System.currentTimeMillis();
System.out.println(end1-now1 + "ms");
}
public static int f(int n, int[] tmp){
if(tmp[n] != 0) return tmp[n];
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
tmp[n] = f(n-1, tmp) + f(n-2, tmp) + f(n-3, tmp);
return f(n-1, tmp) + f(n-2, tmp) + f(n-3, tmp);
}
public static int f1(int n){
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
return f1(n-1) + f1(n-2) + f1(n-3);
}
}
程序运行结果：
1
2
3
41 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 410744 755476 1389537 2555757 4700770 8646064 15902591 29249425
1ms
1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 410744 755476 1389537 2555757 4700770 8646064 15902591 29249425
98ms
机器人走格子：有一个X*Y的网格，一个机器人智能走格点且智能向右或向下走，要从左上角走到有下角。
请设计一个算法，计算机器人有多少种走法。
给定两个正整数int x,int y,请返回机器人的走法数目。保证x+y<=12.
1
2
3
4
5
6
7
8
9public class 机器人走方格{
public static void main(String[] args){
System.out.println(solve(5, 5));
}
public static long solve(int x, int y){
if(x == 1 || y == 1) return 1;
return solve(x-1, y) + solve(x, y-1);
}
}
程序运行结果：
170
合法括号：实现一种算法，打印n对括号的全部有效组和(即左右括号正确配对)。
示例：
输入：3
输出：()()(), (()()), ()(()), (())(), ((()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46import java.util.HashSet;
import java.util.Set;
public class 合法括号{
public static void main(String[] args){
System.out.println(parenthesis(3));
System.out.println(parenthesis1(3));
}
//递归形式
public static Set parenthesis(int n){
Set s_n =new HashSet();
if(n == 1) {
s_n.add("()");
return s_n;
}
Set s_n_1 = parenthesis(n - 1);
for(String s : s_n_1) {
s_n.add("()" + s);
s_n.add(s + "()");
s_n.add("(" + s + ")");
}
return s_n;
}
//迭代形式
public static Set parenthesis1(int n){
Set res =new HashSet();
res.add("()");
if(n == 1) {
return res;
}
for(int i = 2; i <= n; i++) {
Set tmp =new HashSet();
for(String e : res) {
tmp.add("()" + e);
tmp.add(e + "()");
tmp.add("(" + e + ")");
}
res = tmp;
}
return res;
}
}
程序运行结果：
1
2[()()(), (()()), ()(()), (())(), ((()))]
[()()(), (()()), ()(()), (())(), ((()))]
硬币的表示：假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝，用这些硬币组合构成一个给定的数值n。
例如n=200，那么一种可能的组合方式为 200 = 3 1 + 1＊2 + 1＊5 + 2＊20 + 1 50 + 1 * 100.
问总共有多少种可能的组合方式？ (这道题目来自著名编程网站ProjectEuler) 类似的题目还有：
[华为面试题] 1分2分5分的硬币三种，组合成1角，共有多少种组合
1x + 2y + 5*z=10
[创新工厂笔试题] 有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少组合可以组成n分钱
1 5 10 25 分 n,多少种组合方法.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63public class 硬币的表示{
public static void main(String[] args){
System.out.println(countWays(10));
System.out.println(countWays1(10));
System.out.println(countWays2(10));
}
//递归形式
public static int countWays(int n){
if(n <= 0) return 0;
return countWayCore(n, new int[] {1,5,10,25},3);
}
public static int countWayCore(int n, int[] coins, int cur){
if(cur == 0) return 1;
int res = 0;
for(int i = 0; i * coins[cur] <= n; i++) {
int residue = n - i * coins[cur];
res += countWayCore(residue, coins, cur-1);
}
return res;
}
//递推解法
public static int countWays1(int n){
int[] coins = {1, 5, 10, 25};
int[][] dp = new int[4][n + 1];//前i中面值，组合出面值j
for(int i = 0; i < 4; i++) {
dp[i][0] = 1;//凑出面值0,只有一种可能,第一列初始化为1
}
for(int j = 0; j <= n; j++) {
dp[0][j] = 1;//用1来凑任何面值都只有一种凑法,第一行初始化为1
}
/**
* 0 1 2 3 4 5 6
* 1 0 1 1 1 1 1 1
* 5 0 1 1 1 1 2 2
* 10 0
*/
for(int i = 1; i < 4; i++) {
for(int j = 1; j <= n; j++) {
for(int k = 0; k <= j / coins[i]; ++k) {
dp[i][j] += dp[i - 1][j - k * coins[i]];
}
}
}
return dp[3][n];
}
/*递推解法*/
public static int countWays2(int n){
int[] coins = {1, 5, 10, 25};
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 0; i < 4; i++) {
for (int j = coins[i]; j < n + 1; j++) {
dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007;
}
}
return dp[n];
}
}
程序执行结果：
1
2
34
4
4
非空子集生成之二进制法：请编写一个方法，返回某集合的所有非空子集。
给定一个int数组A和数组的大小int n，请返回A的所有非空子集。
保证A的元素个数小于等于20，且元素互异。
各子集内部从大到小排序,子集之间字典逆序排序
java示例代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25import java.util.ArrayList;
import java.util.Arrays;
public class 子集生成及二进制法{
public static void main(String[] args){
char[] A = {'A', 'B', 'C'};
ArrayList> subsets = getSubsets(A, A.length);
System.out.println(subsets);
}
public static ArrayList> getSubsets(char[] A, int n){
Arrays.sort(A);//正序排列
ArrayList> res = new ArrayList<>();//大集合
for(int i = (int) (Math.pow(2, n) - 1); i > 0; i--) { //对每个i建立一个集合
ArrayList s = new ArrayList<>();
for(int j = n - 1; j >= 0; j--) {//检查哪个位上的二进制为1,从高位开始检查,高位对应着数组靠后的元素
if(((i >> j) & 1) == 1){
s.add(A[j]);
}
}
res.add(s);
}
return res;
}
}
程序运行结果：
1[[C, B, A], [C, B], [C, A], [C], [B, A], [B], [A]]
全排列：编写一个方法，确定某字符串的所有排列组合。
给定一个string A和一个int n,代表字符串和其长度，请返回所有该字符串字符的排列，
保证字符串长度小于等于11且字符串中字符均为大写英文字符，
解题思路：以下实现了三种解法：
迭代法
交换法，回溯法
前缀法
java代码示例：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101import java.util.ArrayList;
import java.util.Arrays;
public class 全排列{
public static void main(String[] args){
String A = "ABC";
ArrayList list = getPermutation(A);
System.out.println(list);
list = getPermutation1(A);
System.out.println(list);
getPermutation2("", A.toCharArray());
}
//迭代法
public static ArrayList getPermutation(String A){
int n = A.length();
ArrayList res = new ArrayList<>();
res.add(A.charAt(0) + "");//初始化，包含第一个字符
//第二个字符查到前面生成集合的每个元素里面
for(int i = 1; i < n; i++) {
ArrayList res_new = new ArrayList<>();
char c = A.charAt(i); //新字符
for(String str : res) {//访问上一趟集合中的每个字符串
//插入到每个位置，形成一个新串
String newStr = c + str;//加在前面
res_new.add(newStr);
newStr = str + c;//加在后面
res_new.add(newStr);
//如果字符大于两个的时候，需要加在中间
for(int j = 1; j < str.length(); j++) {
newStr = str.substring(0, j) + c +str.substring(j);
res_new.add(newStr);
}
}
res = res_new;
}
return res;
}
//回溯法(交换法) 多分支递归 非字典序
static ArrayList res = new ArrayList<>();
public static ArrayList getPermutation1(String A){
char[] arr = A.toCharArray();
Arrays.sort(arr);
getPermutationCore(arr, 0);
return res;
}
public static void getPermutationCore(char[] arr, int k){
if( k == arr.length) {
res.add(new String(arr));
}
//从k位开始的每个字符，都尝试放在新排列的k这个位置
for(int i = k; i < arr.length; i++) {
char tmp = arr[i];//将后面的每个字符换到k位
arr[i] = arr[k];
arr[k] = tmp;
getPermutationCore(arr, k + 1);
tmp = arr[i];//回溯
arr[i] = arr[k];
arr[k] = tmp;
}
}
// 前缀法 字典序
public static void getPermutation2(String prefix, char[] arr){
//前缀的长度==字符集的长度时，一个排列就完成了
if(prefix.length() == arr.length) {
System.out.println(prefix);
}
//每次都从头扫描，只要该字符可用，就附加到前缀的后面，前缀变长了
for(int i = 0; i < arr.length; i++) {
char ch = arr[i];
//字符可用：在pre中出现的字数 < 在字符集中的出现次数
if(count(prefix, ch) < count(arr, ch)) {
getPermutation2(prefix + ch, arr);
}
}
}
private static int count(char[] arr, char ch){
int count = 0;
for(int i = 0; i < arr.length; i++) {
if(arr[i] == ch) {
count++;
}
}
return count;
}
private static int count(String prefix, char ch){
int count = 0;
for(int i = 0; i < prefix.length(); i++) {
if(prefix.charAt(i) == ch) {
count++;
}
}
return count;
}
}
程序执行结果
1
2
3
4
5
6
7
8[CBA, BAC, BCA, CAB, ABC, ACB]
[ABC, ACB, BAC, BCA, CBA, CAB]
ABC
ACB
BAC
BCA
CAB
CBA
