2024年JAVA递归试题库.doc

递归
一 基础知识
<1> 递归中每次循环都必须使问题规模有所缩小。
<2> 递归操作的每两步都是有紧密的联系，如在“递归”的“归操作时”，前一次的输出就是后一次的输入。
<3> 当子问题的规模足够小时，必须能够直接求出该规模问题的解，其实也就是必须要有结束递归的条件。

二 递归要处理什么问题呢?
1 不一样的措施体之间的传递
public static void main(String[] args) {
g();
}
private static void g() {
f(3);
}
private static int f(int i) {
return i+k(i);
}
private static int k(int i) {
return i;
}
2 相同的措施体 不一样措施名之间的传递
public static void main(String[] args) {
int i = g(4);
System.out.println(i);
}
private static int g(int i) {
return i*g1(3);
}
private static int g1(int i) {
return i+g2(2);
}
private static int g2(int i) {
return i*g3(1);
}
private static int g3(int i) {
return i;
}
3 看一看得出 其实功效相同因此直接使用递归
public static void main(String[] args) {
int i = g(4);
System.out.println(i);
}
private static int g(int i) {
if(i == 1){
return i;
}
return i*g(i-1);
}
依照 2 与 3 的比较明显的看得出 使用递归明显的缩短了代码的使用量
4 递归的使用框架
返回值类型 f(形参){
if(终止条件){
return 成果;
}
else{
return f(形参递减或者递增);
}
}
5递归算法一般用于处理三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
此类问题虽则自身没有明显的递归结构，
但用递归求解比迭代求解更简单，如汉诺塔
(3)数据的结构形式是按递归定义的。
如二叉树、广义表等，
因为结构自身固有的递归特性，则它们的操作可递归地描述。
三 经典 案例
1 斐波纳契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这么一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的措施定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）
public static int f(int x){
if(x == 0){
return 0;
}
if(x == 1 || x == 2){
return 1;
}
return f(x-1)+f(x-2);
}
2 阶乘
public static int f(int x){
if(x == 1){
return 1;
}else{
return x*f(x-1);
}
}
3全排列
4汉诺塔
public static void hanoi(int n, char origin, char assist, char destination) {
if (n == 1) {
System.out.println("Direction:" + origin + "--->" + destination);
} else {
hanoi(n - 1, origin, destination, assist);
System.out.println("Direction:" + origin + "--->" + destination);
hanoi(n - 1, assist, origin, destination);
}
}
四 试题：
I 递归定义
33.递归的框架 题意试数 字符串反转
/*
我们把“cba”称为“abc”的反转串。 题意就是 对字符串的反转
求一个串的反转串的措施诸多。下面就是其中的一个措施，代码十分简洁（甚至有些神秘），
请聪明的你通过给出的一点点线索补充缺乏的代码。
把填空的答案（仅填空处的答案，不包括题面）存入考生文献夹下对应题号的“解答.txt”中即可。
*/
思绪 就是每次保存最后一位并且放在第一个上返回
或者 每次保存第一个并且放在最后一个
public class Demo03 {
public static String reverseString(String s){
if(s.length()<2||s==null) return s;
//每一次将第一位放在最后，将第二位放在倒数第二位然后进行递归
return reverseString(s.substring(1))+s.charAt(0);
// return s.charAt(s.length()-1) +reverseString(s.substring(0,s.length()-1)); }
public static void main(String[] args){
String s = "123456";
String ss = reverseString(s);
System.out.println(ss);
}
}
运行成果：
654321
132、递归 把串s中第一个出现的数字的值返回。
假如找不到数字，返回-1 例如：
s = "abc24us43" 则返回2
s = "82445adb5" 则返回8
s = "ab" 则返回-1
public static int getFirstNum(String s)
{
if(s==null || s.length()==0) return -1;
char c = s.charAt(0);
if(c>='0' && c<='9') return c-'0'; //填空
return getFirstNum(s.substring(1)); //填空
}
public static void main(String[] args) {
String s = "abs7c24us43";
System.out.println(getFirstNum(s));
}
102.递归的定义 试数 连续数
如下程序打印出0~9的数字，请补充缺乏的代码。
*/
public class 递归连续数 {
public static void f(int begin, int end) {
if(begin>end) return; // 填空
System.out.println(begin);
f(begin + 1, end);
}
public static void main(String[] args) {
f(0, 9);
}
}
运行成果:
0
1
2
3
4
5
6
7
8
9
113.递归定义 题意了解 公交车标价
* 公交车票价为5角。假设每位乘客只持有两种币值的货币：5角、1元。
* 再假设持有5角的乘客有m人，持有1元的乘客有n人。因为特殊情况，开始的时候，售票员没有零钱可找。
* 我们想懂得这m+n名乘客以什么样的次序购票则能够顺利完成购票过程。
* 显然，m < n的时候，无论怎样都不能完成，m >=n的时候，有些情况也不行。例如，第一个购票的乘客就持有1元。
* 下面的程序计算出这m+n名乘客所有也许顺利完成购票的不一样情况的组合数目。
* 注意：只关心5角和1元交替出现的次序的不一样排列，持有同样币值的两名乘客互换位置并不算做一个新的情况来计数。
*/
public class 公交车票价 {
// m: 持有5角币的人数
// n: 持有1元币的人数
// 返回：所有顺利完成购票过程的购票次序的种类数
public static int f(int m, int n) {
if (m < n)
return 0;
if (n == 0)
return 1;
return f(m-1,n) +f (m,n-1); // 填空
}
public static void main(String[] args) {
System.out.println(f(10, 8));
}
运行成果:
11934
147递归 如下程序打印出0~9的数字，请补充缺乏的代码。
public class MyTest
{
public static void f(int begin, int end)
{
If(begin > end) return;
System.out.println(begin);
f(begin+1, end);
}
public static void main(String[] args)
{
f(0,9);
}
}

II排列一般
1 字符排序 全排列
算法是这么的，假如给定N个不一样字符，将这N个字符全排列，最后的成果将会是N!种。如：给定 A、B、C三个不一样的字符，则成果为：ABC、ACB、BAC、BCA、CAB、CBA一共3!=3*2=6种情况。
public class AllPermutation
{
public static void main(String[] args)
{
//使用递归完成全排列
char[] source=new char[]{'A','B','C'};
char[] result=new char[source.length];
allPermutation(0,source,result);

}
/**
*
* @param index目前考虑的数的下标(从0开始)
* @param source
* @param result
*/
public static void allPermutation(int index,char[] source,char[] result){
//当源数据中只有一个字符时，将该字符加入成果数组，并输出
if(source.length==1){
result[index]=source[0];
show(result);
return ;
}
//
for(int i=0;i<result.length-index;i++){
result[index]=source[i];
char[] newSource=getNewSource(source,source[i]);
allPermutation(index+1, newSource,result);
}
}
public static void show(char[] result){
System.out.println(result);
}
/**
* 生成去掉指定字符的新源数据数组
* @param source 本来的源数据数组
* @param c 指定去掉的字符
* @return
*/
public static char[] getNewSource(char[] source,char c){
char[] newSource=new char[source.length-1];
for(int i=0,j=0;i<source.length;i++){
if(source[i]!=c){
newSource[j]=source[i];
j++;
}
}
return newSource;
}
}

42.全排列 递归 Stringbuffer警察智力训练
匪警请拨110,虽然手机欠费也可拨通！
为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要常常性地进行体力训练和智力训练！
某批警察叔叔正在进行智力训练：
1 2 3 4 5 6 7 8 9 = 110;
请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（能够不填，但不能填入其他符号）。之间没有填入符号的数字组合成一个数，
例如：12+34+56+7-8+9 就是一个合格的填法；123+4+5+67-89 是另一个也许的答案。
请你利用计算机的优势，协助警察叔叔迅速找到所有答案。
每个答案占一行。形如：12+34+56+7-8+9123+4+5+67-89......
已知的两个答案能够输出，但不计分。
各个答案的前后次序不重要。
// 遍历所有情况
public static void fun(String v, int n) {
if(n==9){ // 修改到最后一位符号时输出
check(v);
}else{ // 递归向后修改，数字 变为 数字加符号
fun(v.replace(n+"", n+"+"),n+1);
fun(v.replace(n+"", n+"-"),n+1);
fun(v,n+1);
}
}
// 验证 并 输出
public static void check(String str){
String[] s = str.split("[\\+]");
int sum = 0;
for(String t:s){
String[] sub = t.split("[\\-]");
int num = Integer.parseInt(sub[0]);
// 计算负数
for(int i=1;i<sub.length;i++){
num -= Integer.parseInt(sub[i]);
}
sum += num; // 正数或负数成果 加到 总和上
}
if(sum == 110){
System.out.println(str);
}
}
public static void main(String[] args){
String str = "";
fun(str,1); // 调用函数，从1开始修改
}
46算法 实现全排列
递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

publicclassT06 {
// 输出
publicstaticvoid print(List target){
for(Object o: target){
System.out.print(o);
}
System.out.println();
}
// 递归排列
publicstaticvoid sort(List datas,List target,int n){
if(target.size()==n){
print(target);
return;
}
for(int i=0;i<datas.size();i++){
List newDatas = new ArrayList(datas);
List newTarget = new ArrayList(target);
newTarget.add(newDatas.get(i));
newDatas.remove(i);

sort(newDatas,newTarget,n);
}
}
// 主函数
publicstaticvoid main(String[] args){
String[] s = {"a","b","c"};
sort(Arrays.asList(s),newArrayList(),s.length);
}
}
运行成果：
abc
acb
bac
bca
cab
cba

措施二：
publicclassAllSort{
publicstaticvoid perm(String[] buf,int start,int end){
if(start==end){//当只要求对数组中一个字母进行全排列时，只要按该数组输出即可
for(int i=0;i<=end;i++){
System.out.print(buf[i]);
}
System.out.println();
}
else{//多个字母全排列
for(int i=start;i<=end;i++){
String temp=buf[start];//互换数组第一个元素与后续的元素
buf[start]=buf[i];
buf[i]=temp;
perm(buf,start+1,end);//后续元素递归全排列
temp=buf[start];//将互换后的数组还原
buf[start]=buf[i];
buf[i]=temp;
}
}
}
publicstaticvoid main(String[] args) {
String buf[]={"a","b","c"};
perm(buf,0,buf.length-1);
}
}
运行成果：
abc
acb
bac
bca
cba
cab
47.递归 字符串全排列 
字符串全排列
publicclassT03{
// 输出字符数组
publicstaticvoid print(char[] arr){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]);
}
System.out.println();
}
// 递归遍历
publicstaticvoid perm(char[] arr,int start,int end){
if(start==end){
print(arr); // 输出
}else{
for(int i=start;i<=end;i++){
// 换位
char c = arr[start];
arr[start] = arr[i];
arr[i] = c;
// 递归
perm(arr,start+1,end);
// 恢复数组原位
c = arr[start];
arr[start] = arr[i];
arr[i] = c;
}
}
}
// 字符串转字符数组
publicstaticvoid f(String s){
char[] arr = s.toCharArray();
perm(arr,0,arr.length-1);
}
publicstaticvoid main(String[] args){
String s = "abc";
f(s);
}
}
运行成果：
abc
acb
bac
bca
cba
cab
58.递归 全排列 带分数
100 能够表示为带分数的形式：100 = 3 + 69258 / 714
还能够表示为：100 = 82 + 3546 / 197
注意特性：带分数中，数字1~9分别出现且只出现一次（不包括0）。
类似这么的带分数，100 有 11 种表示法。
题目要求：
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的所有种数。
注意：不要求输出每个表示，只统计有多少表示法！
例如：
用户输入：
100
程序输出：
11
再例如：
用户输入：
105
程序输出：
6
资源约定：
峰值内存消耗（含虚拟机）< 64M
CPU消耗< 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...”的多出内容。
所有代码放在同一个源文献中，调试通过后，拷贝提交该源码。
public class MyTest {
private static Set<Integer> all = new HashSet<Integer>();
private static Set<Integer> temp1 = new HashSet<Integer>();
private static Set<Integer> temp2 = new HashSet<Integer>();
public static void main(String[] args) {
for(int i= 1; i<9876; i++) {
all.clear();
if(isDuplicate(i, temp1)) {
continue;
}
for(int j = 2; j<100; j++) {
if(!isDuplicate(j*i, temp1)) {
int y = 100-j;
if(!isDuplicate(y, temp2) && all.size()==9) {
System.out.println(100 + "=" + y + "+" + j*i + "/" + i);
}else {
all.removeAll(temp1);
}
}
}
}
}
private static boolean isDuplicate(int n, Set<Integer> temp) {
temp.clear();
int i = 0;
boolean flag = false;
while(n>0) {
int x = n % 10;
temp.add(x);
n = n/10;
i++;
}
if(temp.contains(0) || temp.size()<i || temp.removeAll(all)) {
flag = true;
}else {
all.addAll(temp);
}
return flag;
}
}
92. 全排列 排列组合 数组列表 m个字符的n个字符排列
/*
* 1~9个数中的n位数全排列
*/
static int count = 0; // 总个数
/**
* 全排列
* @param lis 统计组合
* @param start 为0~9(lis所用的下标)
* @param end 为9
*/
public static void f(List<Integer> lis,int start){
if(start>=lis.size()){
System.out.println(lis); // 输出排列组合
count++; // 计数
return ;
}
for(int i=1;i<=9;i++){
if(!lis.contains(i)){
lis.set(start, i); // 修改元素
}else{
continue;
}
f(lis,start+1); // 递归修改每个元素
lis.set(start, -1); // 还原
}
}
public static void main(String[] args){
int n = 5; // 1~9个数中选5个全排列
List<Integer> lis = new ArrayList<Integer>();
for(int i=0;i<n;i++){ // 初始化lis长度
lis.add(-1);
}
f(lis,0); // 全排列
System.out.println("总个数:"+count);
}

运行成果:
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 6]
[1, 2, 3, 4, 7]
[1, 2, 3, 4, 8]
[1, 2, 3, 4, 9]
[1, 2, 3, 5, 4]

...............

...............

...............

[9, 8, 7, 5, 6]
[9, 8, 7, 6, 1]
[9, 8, 7, 6, 2]
[9, 8, 7, 6, 3]
[9, 8, 7, 6, 4]
[9, 8, 7, 6, 5]
总个数:15120

措施二:对以上程序的 (数字排列)扩展为(字符排列)看下程序:
import java.util.ArrayList;
import java.util.List;

public class T13 {
static int count = 0; // 统计个数
// m排n全排列
public static void f(List<Character> lis,char[] c,int n){
if(n==0){
count++; // 统计个数
System.out.println(lis); // 输出
return ;
}
for(int i=0;i<c.length;i++){
if(!lis.contains(c[i])){ // 不包括,则添加
lis.set(lis.size()-n, c[i]);
}else{ // 否则跳过
continue;
}
f(lis,c,n-1); // 递归
lis.set(lis.size()-n, '0'); // 还原
}
}
public static void main(String[] args) {
long star = System.currentTimeMillis();
int n = 3; // 任选n个字符的排列组合
char[] c = "".toCharArray(); // 要排列的字符
List<Character> lis = new ArrayList<Character>();
for(int i=0;i<n;i++){
lis.add('0'); // 初始化 lis 的长度
}
f(lis,c,n); // 进入全排列
System.out.println("排列个数:"+count);
System.out.println("花费时间:"+(System.currentTimeMillis()-star)+"毫秒");
}
}

运行成果:
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 2, 7]
[1, 2, 8]
[1, 2, 9]
[1, 3, 2]

.........

.........

.........

[9, 7, 8]
[9, 8, 1]
[9, 8, 2]
[9, 8, 3]
[9, 8, 4]
[9, 8, 5]
[9, 8, 6]
[9, 8, 7]
排列个数:504
花费时间:19毫秒

措施三:
/*
* m个字符的n个字符排列
*/
import java.util.ArrayList;
import java.util.List;

public class m个字符的n个字符排列 {
private static char[] is = new char[] { '1', '2', '3', '4', '5', '6', '7', '8', '9'};
private static int total;
private static int m = 4;
private void plzh(String s, List<Integer> iL, int m) {
if(m == 0) {
System.out.println(s);
total++;
return;
}
List<Integer> iL2;
for(int i = 0; i < is.length; i++) {
iL2 = new ArrayList<Integer>();
iL2.addAll(iL);
if(!iL.contains(i)) {
String str = s + is[i];
iL2.add(i);
plzh(str, iL2, m-1);
}
}