算法-递归

概述

　　递归是一个过程或函数在定义中直接或间接调用自身的一种方法。递归算法设计，就是把一个大型的问题层层转化为一个与原问题相似的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到原大型问题的解。

　　一般来说，递归需要有边界条件，递归前进段和递归返回段。当边界条件不满足时，递归前进：当边界条件满足时，递归返回。

如一下代码：

1
2
3
4

int f(int n){
    if(n==1) return 1;
    return n*sum(n-1);
}

上面的代码是求n！，输入4，则执行 4^f(3)- >4^3^f(2)- > 4^3^2^f(1)- >4^3^2^1

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

1. 数据的定义是按递归定义的

2. 问题解法按递归算法实现。

   这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单

3. 数据的结构形式是按递归定义的。

   如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

缺点

　　递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。

相关题目

1.FJ的字符串

问题描述：

　　FJ在沙盘上写了这样一些字符串：
　　A1 = “A”
　　A2 = “ABA”
　　A3 = “ABACABA”
　　A4 = “ABACABADABACABA”
　　… …
　　你能找出其中的规律并写所有的数列AN吗？

输入格式

　　仅有一个数：N ≤ 26。

输出格式

　　请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入

3

样例输出

ABACABA

分析

一道很简单的递归题目，很明显这是二叉树的中序遍历，用递归进行二叉树的中序遍历即可

1
2
3
4
5
6
7
8
9
10

public static void f(int n){
	if(n==0){
		System.out.print('A');
	}else {
		f(n-1);
		System.out.print((char)('A'+n));
		f(n-1);
	}
		
}

2.排队购票问题

　　一场电影开始前，售票工作正在紧张进行中。每张电影票为50元，现在有i个人排队等待购票，其中有m个人手持50元的钞票，另外n个人手持100元的钞票。假设开始售票时售票处没有零钱，求出这i个人排队购票，使售票处不至出现找不开钱的局面的不同排队种数（拿同样面值钞票的人对换位置为同一种排队）

分析

　　令recuision(int m,int n)表示有m个人拿的是50元钞票，n个人拿的是100元钞票，那么有一下三种情况：

1. n=0 意味着购买票的全是拿50元的，那么这i个人的排队总数为1 ,即recuision(m,0)=1;

2. m<n 排队买票的人数里拿50元的小于拿100元的 ，这时不管怎么排队都会出现找不开钱的局面，即recuision(m,n)=0

3. 其他 在m+n个排队购票，第m+n个人站在第m+n-1个人的后面，则第m+n个人的排队方式可由下列两种方式获得

   1. 第m+n个人拿的是100元钞票，则在他前面的m+n-1个人中，有m个拿的是50元钞票，有n-1个人拿的是100元钞票，这种情况有ecursion(m,n-1)
   2. 第m+n个人拿的是50元钞票，则在他前面的m+n-1个人中，有m-1个拿的是50元钞票，有n个人拿的是100元钞票，这种情况有ecursion(m-1,n)

   那么可以获得递推关系:recursion(m+n)=recursion(m,n-1)+recursion(m-1,n)

边界条件为：

• 当n=0时 recursion(m,n)=1
• 当m<n时 recursion(m,n)=0;

代码

1
2
3
4
5

public static long recursion(int m,int n){
	if(n==0) return 1;
	if(m<n) return 0;
	return recursion(m,n-1)+recursion(m-1,n);
}

3.幂方分解

问题描述

　　任何一个正整数都可以用2的幂次方表示。例如：
　　137=27+23+20
　　同时约定方次用括号来表示，即ab 可表示为a（b）。
　　由此可知，137可表示为：
　　2（7）+2（3）+2（0）
　　进一步：7= 22+2+20 （21用2表示）
　　3=2+20
　　所以最后137可表示为：
　　2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　又如：
　　1315=210 +28 +25 +2+1
　　所以1315最后可表示为：
　　2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）

输入格式

　　输入包含一个正整数N（N<=20000），为要求分解的整数。

输出格式

　　程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）

分析

创建一个一维数组用来存放2的幂方int ar[]{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384}

创建递归函数f(int n) n为待分解的数，递归出口：

• n=0 return ;
• n=1 System.out.print(“2(0)”); return ;
• n=2 System.out.print(“2”); return ;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void f(int n){
		int i=14;
		if(n==0) return ;
		if(n==1){
			System.out.print("2(0)"); return ;
		}
		if(n==2){
			System.out.print("2"); return ;
		}
		while(ar[i]>n&&i>=0) i--;
		System.out.print("2");
		if(i>1){
			System.out.print("(");
			f(i);
			System.out.print(")");
		}
		n=n-ar[i];
		if(n>0)
			System.out.print("+");
		f(n);		
	}

4.瓷砖铺放

问题描述

　　有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
　　例如，长度为4的地面一共有如下5种铺法：
　　4=1+1+1+1
　　4=2+1+1
　　4=1+2+1
　　4=1+1+2
　　4=2+2
　　编程用递归的方法求解上述问题。

输入格式

　　只有一个数N，代表地板的长度

输出格式

　　输出一个数，代表所有不同的瓷砖铺放方法的总数

样例输入

4

样例输出

5

分析

创建递归函数f(int i) 调用函数时给i赋值0 创建count代表次数

每次通过判断i+1和i+2是否大于等于n 来调用f(i+1) f(i+2)

递归出口：

• i=n count++; return ;

代码

1
2
3
4
5
6
7
8
9
10
11
12

public static void f(int i){
		if(i==n){
			count++; return ;
		}
		if(i+1<=n){
			f(i+1);
		}
		if(i+2<=n){
			f(i+2);
		}
		return ;
	}

5.s01串

问题描述

　　s01串初始为”0”
　　按以下方式变换
　　0变1，1变01

输入格式

　　1个整数(0~19)

输出格式

　　n次变换后s01串

样例输入

3

样例输出

101

分析

很简单的一道题，就是让字符串不断转换，用循环可以轻松解决，不过这里我要用递归代替循环

创建递归函数f(int n) n表示需要转换的次数 ，当n>0时调用转换函数f1，在调用自身f(n-1) ,递归出口：

• n==0 return ;

代码:

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

import java.util.Scanner;

public class s01串 {
	static StringBuilder str;
	static int n;
	public static void main(String[] args) {
		str=new StringBuilder().append("0");
		Scanner in =new Scanner(System.in);
		n=in.nextInt();
		f(n);
		System.out.println(str);
	}
	public static void f(int n){
		if(n==0){
			return ;
		}else{
			f1();
			f(n-1);
		}
	}
	public static void f1(){
		String s=str.toString();
		str.delete(0, str.length());
		for(int i=0;i<s.length();i++){
			str.append(to(s.charAt(i)));
		}
	}
	public static String to(char c){
		if(c=='0'){
			return "1";
		}else if(c=='1')
			return "01";
		return "";
	}
}

6.最优路径搜索

​ 点数值三角形是一个二维数组：三角形由n行构成，第k行有k个点，每一个点都带有一个数值。寻找从顶点开始每一步可沿左斜或右斜向下至底的一条路径，使该路径所经过的点的数值和最小。

比如输入n为3，三角形为：

口

口 口

口 口 口

分析

三角形可用一个二维数组存储arr[ ] [ ] min表示最短路径，创建递归函数f(int i,int j) 表示点arr[i] [j] 的最小值，那么从f(0,0)开始，f(0,0)由min{f(1,0),f(1,1)}确定，则得到递推式:min=f(i,j)+min{f(i+1,j),f(i+1,j+1)}

递归出口:

• i=n-1 return arr[i] [j]

代码

1
2
3
4

public static int f(int i,int j){
		if(i==n-1) return arr[i][j];
		return arr[i][j]+Math.min(f(i+1,j), f(i+1,j+1));
	}

ps:这道题用递归计算的话会导致很多的重复计算，用动态规划解决的话效率会更高

总结

　　使用递归写出来的代码一般都是非常简洁的，但是有可能会导致很多的重复计算，从而导致运行效率变低。一些简单的问题可以考虑用递归来解决，但是较为复杂的问题，递归往往不是首选。