大家好,又见面了,我是你们的朋友全栈君。
1.递归算法
1.1递归的概念
所谓递归,就是程序方法在运行过程中自身调用自身。定义如下所示。
fn(){
if(递归出口条件){
return x;
}else{
//some codes…
return fn();
}
}
1.2递归的使用条件
1.2.1 必须要有明确的递归出口
所谓递归出口就是需要有明确的结束条件。
1.2.2 每次递归都要使问题的规模减小
1.2.3 递归的规模不能太大
如果递归次数太多,很容易造成内存泄露。
1.3递归的优点及缺点
递归是一种算法策略。在二叉树、广义链表的节点遍历情景中,具有很重要的价值。事实上,递归与循环是解决遍历数据问题的两种不同的思路。对于循环而言,效率高是它的一大显著特点,不会占用额外的内存开销,但也有缺点,使用循环写的代码可读性不强,而且代码往往冗长;对于递归而言,效率方面较循环要逊色一些,因为递归需要开辟额外的内存空间,但优点是其代码简洁清爽,较为严谨,在解决某些特殊问题,又不得不使用递归来求解。一般地,递归问题都能转换为循环进行求解。
1.4递归举例
1.4.1 字符串反向输出
描述:输入字符串abc,要求能输出cba,以此类推。
分析:我们可以这样来考虑这个问题,cba=c+ba,这样,这个问题的规模就化解为了一个字母与ba这个字符串进行拼接,也就是f(3) = c+f(2)=cb+f(1),每递归一次,数组长度就减1,直到数组长度为0时,就是递归出口。代码如下所示。
package com.yzh.maven.main;
public class Digui {
static int length = 0;
public static void main(String[] args) {
System.out.println(reverse("abcsdfg".toCharArray()));
}
public static String reverse(char[] c){
length = c.length;
String obj = "";
//递归出口
if(length == 0){
return obj;
}else{
//获取当前元素
obj = c[--length]+"";
//定义中间数组
char[] c1 = new char[length];
//变为长度-1,问题规模减小
System.arraycopy(c,0,c1,0,length);
return obj+reverse(c1);
}
}
}
1.4.2 斐波纳契数列问题
描述:求1,1,2,3,5,8,13…数列的第n项。
分析:我们注意到,该数列从第三项开始,其数值等于前两项之和。这个表达式可以用fn(n) = fn(n-1)+fn(n-2) (n>2)来表示。当n=1或n=2时,可以直接获取结果,因此可以作为递归的出口;而fn(n-1) = fn(n-2)+fn(n-3),我们看到,该问题再向出口一步步靠近,也就是问题规模在不断减小,因此满足递归的条件。代码实现如下所示。
public static int fibonacci(int n){
//递归出口
if(n == 1 || n == 2){
return 1;
}else{
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
1.4.3阶乘问题
描述:求n!。
分析:对于阶乘,我们同样可以使用递归求解。我们令fn(n)=!n,那么fn(n-1)=(n-1)!,从而fn(n)=nfn(n-1),当n=1时,那么fn(1)=10!=1,能够直接获得的结果可以作为递归出口,同时,我们看到阶乘的规模在一步步减小,直到直接获得作为递归出口的结果。代码如下所示。
public static int factorial(int n){
//递归出口
if(n == 1){
return 1;
}else{
return n*factorial(n-1);
}
}
1.4.4单链表节点数据的遍历
分析:我们知道,单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息(需要存储的数据),另一个部分存储下一个节点的地址,也就是指针域。最后一个节点存储地址的部分指向空值。我们可以利用这个空值来作为单链表节点数据的遍历的递归出口,代码如下所示。
节点模型:
package com.yzh.maven.main;
public class Node {
private Object data;
private Node nextNode;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
}
取出所有的节点数据:
public static void showAllNodeData(Node node){
//递归出口
if(null == node){
return;
}else{
System.out.print(node.getData()+"->");
showAllNodeData(node.getNextNode());
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/156720.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...