首页 / 算法 / java数据结构和算法-06-递归
java数据结构和算法-06-递归
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java数据结构和算法-06-递归，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4491字，纯文字阅读大概需要7分钟。
内容图文
1.递归简介
递归简单来说就是一种方法（或者说函数）调用自己的技术。递归做为一种算法在程序设计语言中广泛应用。
特点
>调用自身
>调用自身是为了解决更小的问题
递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。的递归能力在于用有限的语句来定义对象的无限集合。
> 递归需要有边界条件，递归前进段和递归返回段。
边界即存在足够简单的问题层次，这一层算法不需要调用自己就可以直接解答，并且返回结果。
当边界条件不满足时，递归前进;当边界条件满足时，递归返回。
优点
>把通常一个大型复杂的问题层层转化为一个与原问题形容词：的规模较小的问题来求解。
缺点
>低效性
调用一个方法会有额外的内存开销，控制从方法的调用处转移到方法的开始处，初次之外方法的参数和地址都要被压入到一个内部栈里面，为的是可以知道要访问的方法和参数的位置。如果因为递归造成大规模的方法调用的话，大量的中间参数和返回值可能会造成内存泄漏。调用递归不一定为了高效，而是为了简化问题。
2.三角数字
已知有个数字序列为1,3,6,10,15,21 ......，则对应的三角模型如下图，
图解
上面的数字数列是三角数字模型的抽象结果，我们可以看出第一项有一列，一列有一个方块，第二项有两列，左边一列两个方块，右边一列一个方块，后面第Ñ项有ñ列，从右到左一次递增。则猜想第ñ项有1 + 2 + 3 + ... +（N-1）+ N个小方块。
数学归纳法
递归是程序设计中的数学归纳法，即通过自身的语汇来定义某事物自己的方法，我们用数学的方式来定义三角数字。
如果n = 1，则tri（n）= 1）
tri（n）= n + tri（n-1）if（n> 1）
代码求解第ñ项大小
package chap6_递归_三角数字;
//1,3,6,10,15,21.....
public class TriXh {
public static void main(String[] args) {
int n = 4;
int total = getTri(n);
int total2 = getTri2(n);
System.out.println(total);
System.out.println(total2);
}
// 循环
private static int getTri(int n) {
int total = 0;
while (n > 0) {
total = total + n;
n--;
}
return total;
}
// 递归
private static int getTri2(int n) {
if (n == 1) {
return 1;
} else {
return n+getTri2(n-1);
}
}
}
查看实际调用以及栈模型模拟
package chap6_递归_三角数字;
//1,3,6,10,15,21.....
public class TriXh2 {
public static void main(String[] args) {
int n = 5;
int total2 = getTri2(n);
System.out.println(total2);
}
// 递归
private static int getTri2(int n) {
System.out.println("Entering n= "+n);
if (n == 1) {
System.out.println("Returning 1");
return 1;
} else {
int temp = n+getTri2(n-1);
System.out.println("Returning temp= "+temp);
return temp;
}
}
}
运行结果
Entering n= 5
Entering n= 4
Entering n= 3
Entering n= 2
Entering n= 1
Returning 1
Returning temp= 3
Returning temp= 6
Returning temp= 10
Returning temp= 15
15
栈模拟
getTri2（）方从参数5开始，方法反复调用自身，参数依次减1，减到1时，开始一序列的返回
阶乘
阶乘和三角数字类似，只有用乘法取代加法
代码求解第ñ项大小
package chap6_递归_阶乘;
public class FacTest {
public static void main(String[] args) {
int n = 5;
int result = getFac(n);
System.out.println(result);
}
private static int getFac(int n) {
if(n ==1){
return 1;
}else{
return n*getFac(n-1);
}
}
}
变位字
变位字可以理解为一种组合，或者一种排列的方式，列出一个对象所有的组合方式可以称为变位一个对象或者全排列。
代码
package chap6_递归_变位字;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class AnagramApp {
static int size;
static int count;
static char[] arrChar = new char[100];
public static void main(String[] args) throws IOException {
System.out.println("Enter a word: ");
String input = getString();
size = input.length();
count = 0;
for (int i = 0; i < size; i++) {
arrChar[i] = input.charAt(i);
}
doAnagram(size);
}
private static void doAnagram(int newSize) {
if (newSize == 1) {
return;
}
for (int j = 0; j < newSize; j++) {
doAnagram(newSize - 1);
if (newSize == 2) {
dispalyWord();
}
rotate(newSize);
}
}
private static void rotate(int newSize) {
int j;
int position = size - newSize;
char temp = arrChar[position];
for (j = position + 1; j < size; j++) {
arrChar[j - 1] = arrChar[j];
}
arrChar[j - 1] = temp;
}
private static void dispalyWord() {
if (count < 99) {
System.out.print(" ");
}
if (count < 9) {
System.out.print(" ");
}
System.out.print(++count + " ");
for (int j = 0; j < size; j++) {
System.out.print(arrChar[j]);
}
System.out.print(" ");
System.out.flush();
if (count % 6 == 0) {
System.out.println("");
}
}
private static String getString() throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}
运行结果
Enter a word:
word
1 word 2 wodr 3 wrdo 4 wrod 5 wdor 6 wdro
7 ordw 8 orwd 9 odwr 10 odrw 11 owrd 12 owdr
13 rdwo 14 rdow 15 rwod 16 rwdo 17 rodw 18 rowd
19 dwor 20 dwro 21 dorw 22 dowr 23 drwo 24 drow
内容总结
以上是互联网集市为您收集整理的java数据结构和算法-06-递归全部内容，希望文章能够帮你解决java数据结构和算法-06-递归所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。