今天说说递归思想,在我们编码时,有的时候递归能够让我们的算法更加通俗易懂,并且代码量也是大大的减少。比如我先前的系列中说到了
关于树的“先序,中序和后序”遍历,那么看看用递归来描叙这个问题是多少的简洁,多么的轻松。
#region 二叉树的先序遍历
/// <summary>
/// 二叉树的先序遍历
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="tree"></param>
public void BinTree_DLR<T>(ChainTree<T> tree)
{
if (tree == null)
return;
//先输出根元素
Console.Write(tree.data + "\t");
//然后遍历左子树
BinTree_DLR(tree.left);
//最后遍历右子树
BinTree_DLR(tree.right);
}
#endregion
#region 二叉树的中序遍历
/// <summary>
/// 二叉树的中序遍历
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="tree"></param>
public void BinTree_LDR<T>(ChainTree<T> tree)
{
if (tree == null)
return;
//优先遍历左子树
BinTree_LDR(tree.left);
//然后输出节点
Console.Write(tree.data + "\t");
//最后遍历右子树
BinTree_LDR(tree.right);
}
#endregion
#region 二叉树的后序遍历
/// <summary>
/// 二叉树的后序遍历
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="tree"></param>
public void BinTree_LRD<T>(ChainTree<T> tree)
{
if (tree == null)
return;
//优先遍历左子树
BinTree_LRD(tree.left);
//然后遍历右子树
BinTree_LRD(tree.right);
//最后输出节点元素
Console.Write(tree.data + "\t");
}
#endregion
看看,多么简洁明了。当然递归都是可以改成非递归的,但是就不见得简洁和通俗易懂了。
一: 概念
递归,说白了就是直接或者间接的调用自己的一种算法。它是把求解问题转化为规模较小的子问题,然后通过多次递归一直到可以得出结果
的最小解,然后通过最小解逐层向上返回调用,最终得到整个问题的解。总之递归可以概括为一句话就是:“能进则进,不进则退”。
二:三要素
<1> 递归中每次循环都必须使问题规模有所缩小。
<2> 递归操作的每两步都是有紧密的联系,如在“递归”的“归操作时”,前一次的输出就是后一次的输入。
<3> 当子问题的规模足够小时,必须能够直接求出该规模问题的解,其实也就是必须要有结束递归的条件。
三: 注意
<1> 前面也说了,递归必须要有一个递归出口。
<2> 深层次的递归会涉及到频繁进栈出栈和分配内存空间,所以运行效率比较低,当问题规模较大时,不推荐使用。
<3> 在递归过程中,每次调用中的参数,方法返回点,局部变量都是存放在堆栈中的,如果当问题规模非常大时,容易造成堆栈溢出。
四: 举二个例子
<1> 相信大家在初中的时候都学过阶乘吧,比如:5!=5*4*3*2*1
思路:根据上面的阶乘特征很容易我们就可以推导出n!=n*(n-1)*(n-2)....*2*1,
那么进一步其实就是: n!=n*(n-1)! ,
(n-1)!=(n-1)*(n-2)!。
显然他是满足递归的三要素,当n的规模不大时,我们可以用递归拿下。
@Test
public void testJC() {
while (true) {
// 阶乘问题
System.out.println("请输入一个求阶乘的一个数:");
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
System.out.println("阶乘的结果为:" + fact(num));
}
}
public int fact(int n) {
if (n == 1)
return 1;
return n * fact(n - 1);
}
第一次: 输入5的时候能够正确求出。
第二次: 输入10的时候求出来竟然362万之多,可见多恐怖,如果俺们的时间复杂度是n!,那程序也就Game Over了,
第三次:输入100,已经超过了int.MaxValue了,
第四次: 输入10w,蹦出著名了“堆栈溢出”,好家伙,我们知道“递归”在程序中使用“栈”的形式存放的,每一次“递归”中,方法的返回值
包括函数中的参数都会存放在栈中,C#中每个线程分配的栈空间为1M,所以当N的规模非常大时,就把栈玩爆了。
<2> 在大一时上计算机文化基础的时候我们就接触过”进制转换问题“,比如将”十进制“转化为”二进制“。
思路:采用除2取余法,取余数为相应二进制数的最低位,然后再用商除以2得到次低位.......直到最后一次相除商为0时得到二进制的最高位,
比如(100)10=(1100100)2, 仔细分析这个问题,会发现它是满足”递归“的三要素的,
① 进制转换中,数据规模会有所缩小。
② 当商为0时,就是我们递归的出口。
所以这个问题我们就可以用递归拿下。
private StringBuffer mm = new StringBuffer();
@Test
public void testConvertToBinary() {
int num = 100;
convertToBinary(num);
System.out.println("十进制数字:"+num+", 转换为二进制为:"+mm);
}
public void convertToBinary(int num) {
int a = num % 2;
num = num / 2;
if (num > 0) {
convertToBinary(num);
}
mm.append(a);
}
扩展其他方式:
1、循环实现
@Test
public void test3(){
int a = 100;
String s ="";
while(a>0){
s = a%2 + s;
a /= 2;
}
System.out.println(s);
}
2、 java API实现
@Test
public void test2(){
int a = 100;
System.out.println(Integer.toBinaryString(a));
}
参考:http://blog.csdn.net/m13666368773/article/details/7531463
分享到:
相关推荐
CPPC++_PCLPoint Cloud Library点云库学习记录
基于Python的百度百科爬虫
CPPC++_Qt 之 GUI 控件使用 网络 架构原理 运行机制理解DTK 重绘控件方式的框架解析IDE 技巧
10020
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
cppc++
2000d
Apache Kafka:Kafka集群运维与监控.docx
CPPC++_TNN是由腾讯优图实验室和光影实验室共同开发的一种面向移动桌面和服务器的统一深度学习推理框架,TNN具有
huluxia.apk
Python商品销售数据分析可视化项目源码(期末大作业).zip,个人经导师指导并认可通过的98分大作业设计项目。主要针对计算机相关专业的正在做期末大作业设计的学生和需要项目实战练习的学习者,可作为课程设计、期末大作业,代码资料完整下载可用。 Python商品销售数据分析可视化项目源码(期末大作业).zip,个人经导师指导并认可通过的98分大作业设计项目。主要针对计算机相关专业的正在做期末大作业设计的学生和需要项目实战练习的学习者,可作为课程设计、期末大作业,代码资料完整下载可用。Python商品销售数据分析可视化项目源码(期末大作业).zip,个人经导师指导并认可通过的98分大作业设计项目。主要针对计算机相关专业的正在做期末大作业设计的学生和需要项目实战练习的学习者,可作为课程设计、期末大作业,代码资料完整下载可用。Python商品销售数据分析可视化项目源码(期末大作业).zip,个人经导师指导并认可通过的98分大作业设计项目。主要针对计算机相关专业的正在做期末大作业设计的学生和需要项目实战练习的学习者,可作为课程设计、期末大作业,代码资料完整下载可用。Python商品销售数据分析
[CSP-J 2023] 小苹果的代码
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手
基于SVM的简单机器学习分类,可以使用svm,knn,朴素贝叶斯,决策树四种机器学习方法进行分类
基于YOLOv5和PSPNet的实时目标检测和语义分割系统Python实现源码+文档说明(高分毕设),该项目是个人毕设项目,答辩评审分达到98分,代码都经过调试测试,确保可以运行!欢迎下载使用,可用于小白学习、进阶。该资源主要针对计算机、通信、人工智能、自动化等相关专业的学生、老师或从业者下载使用,亦可作为期末课程设计、课程大作业、毕业设计等。项目整体具有较高的学习借鉴价值!基础能力强的可以在此基础上修改调整,以实现不同的功能。 基于YOLOv5和PSPNet的实时目标检测和语义分割系统Python实现源码+文档说明(高分毕设)基于YOLOv5和PSPNet的实时目标检测和语义分割系统Python实现源码+文档说明(高分毕设)基于YOLOv5和PSPNet的实时目标检测和语义分割系统Python实现源码+文档说明(高分毕设)基于YOLOv5和PSPNet的实时目标检测和语义分割系统Python实现源码+文档说明(高分毕设)基于YOLOv5和PSPNet的实时目标检测和语义分割系统Python实现源码+文档说明(高分毕设)基于YOLOv5和PSPNet的实时目标检测和语义分割系统Pyt
CPPC++_通过carlarosbridge在carla上实现自动驾驶planning and control
cppc++
分布式事务管理