递归算法

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 4,110 | 阅读时长： 21

递归算法

​ 在函数或子过程的内部，直接或者间接地调用自己的算法。

特点：

  • (1) 递归就是在过程或函数里调用自身。
  • (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
  • (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
  • (4) 在 递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成 栈溢出等。所以一般不提倡用递归算法设计程序。

递归算法一般用于解决三类问题：

递归设计经验：

  • 找重复（子问题）
  • 找重复中的变化量–>参数
  • 找参数变化趋势 –> 设计出口

解递归的常见思路：

  1. 切蛋糕思维，如求阶乘f(n) = n * f(n-1)，数组就和，翻转字符串。
  2. 化不开的，看有没有递推公式？有没有等价转化？ 如：斐波那契数列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<stdho.h>
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<stdio.h>
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<stdio.h>
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. 两项求和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public 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);
	}
}

运行结果:

1
1 1 2 3 5 8 13 21 34

最大公约数：

1
2
3
4
5
6
7
8
9
public 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);
	}
}

程序运行结果：

1
6

插入排序改递归：

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
public 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;
	}
}

程序运行结果：

1
0 2 3 4 6 9 18

汉诺塔问题：

将1-N从A移动到B，C作为辅助。等价于：

  1. 1~N-1移动到C，A作为源，B作为辅助
  2. 把N从A移动到B
  3. 把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
27
public 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
5
1: A-->B
2: A-->C
1: B-->C
3: A-->B
1: C-->A

二分查找递归解法：

全范围二分查找，等价于三个子问题：

  1. 左边找（递归）
  2. 中间比
  3. 右边找（递归）

注意：左边查找和右边查找只选其一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public 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
	}
}

程序运行结果：

1
3

递归算法的性能分析：

递归性能

斐波那契数列递归实现改进：

通过记录每次f(n)的值来防止大量重复计算，大大增加了性能。

1
2
3
4
5
6
7
8
9
10
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);
		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
38
public 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("<" + fibonacci(n-1) + fibonacci(n-2)+ ">") ;
		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("<" + tmp[n] + ">");
		count1++;
		return fib(n-1, tmp) + fib(n-2, tmp);
	}
}

程序运行结果：

1
2
3
4
1 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
39
public 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
4
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 
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
9
public 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);
	}
}

程序运行结果：

1
70

合法括号：

实现一种算法，打印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
46
import 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<String> parenthesis(int n){
		Set<String> s_n =new HashSet<String>();
		if(n == 1) {
			s_n.add("()");
			return s_n;
		}
		Set<String> 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<String> parenthesis1(int n){
		Set<String> res =new HashSet<String>();
		res.add("()");
		if(n == 1) {
			return res;
		}
		for(int i = 2; i <= n; i++) {
			Set<String> tmp =new HashSet<String>();
			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
63
public 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
3
4
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
25
import java.util.ArrayList;
import java.util.Arrays;

public class 子集生成及二进制法 {
	public static void main(String[] args) {
		char[] A = {'A', 'B', 'C'};
		ArrayList<ArrayList<Character>> subsets = getSubsets(A, A.length);
	    System.out.println(subsets);
	}
	
	public static  ArrayList<ArrayList<Character>> getSubsets(char[] A, int n){
		Arrays.sort(A);//正序排列
		ArrayList<ArrayList<Character>> res = new ArrayList<>();//大集合
		for(int i = (int) (Math.pow(2, n) - 1); i > 0; i--) { //对每个i建立一个集合
			ArrayList<Character> 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且字符串中字符均为大写英文字符，

解题思路：

以下实现了三种解法：

  1. 迭代法
  2. 交换法，回溯法
  3. 前缀法

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
101
import java.util.ArrayList;
import java.util.Arrays;


public class 全排列 {
	public static void main(String[] args) {
		String A = "ABC";
		ArrayList<String> list = getPermutation(A);
		System.out.println(list);
		list = getPermutation1(A);
		System.out.println(list);
		getPermutation2("", A.toCharArray());
	} 
	
	//迭代法
	public static ArrayList<String>  getPermutation(String A){
		int n = A.length();
		ArrayList<String> res = new ArrayList<>();
		res.add(A.charAt(0) + "");//初始化，包含第一个字符
		//第二个字符查到前面生成集合的每个元素里面
		for(int i = 1; i < n; i++) {
			ArrayList<String> 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<String> res = new ArrayList<>();
	public static ArrayList<String> 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
坚持原创技术分享，您的支持将鼓励我继续创作！