#Java算法设计与分析1–递归算法
大家好，又见面了，我是你们的朋友全栈君。
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());
}
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/156720.html原文链接：https://javaforall.cn
腾讯云开发者
