很久没有写技术博客了。
最近发现,递归是一个很有用的东西,在有些情况下可以大大提高程序的效率,但是在某些情况(比如某些计数实现时)会好用大量的时间和空间,甚至可能导致系统崩溃。但是,它无可否认是一个很强大的问题解决技术。比如,我们在建立一个二叉树时,就用到了递归的思想。
有人说过,递归就像两面相对放置的镜子,我们可以在一面镜子中看到另一面镜子的镜像,而且镜像在逐步变小。这也就意味着,我们在解决问题时,可以一样地大化小,小化无。我们在使用递归时,一般都是找一个base case作为递归的基例,然后再逐渐让程序往base case上靠拢。
下面直接上例子吧。
/**
* Output 1 ~ n.
* @param n
*/
public static void output(int n){
// base case
if(n == 1){
System.out.printf("%d ", n);
} // end if
// recurse
if(n > 1){
System.out.printf("%d ", n);
output(n - 1);
} // end if
} // end output
这是一个很简单的递归调用,用来实现一串数字的打印。其中,基例(base case)就是n==1的情况,以后的每一次的调用,都逐渐向着这一目标有规律地靠近。当然,这个问题可以用迭代的方法来实现,这里只是用以说明递归而已。下面的一个例子也是一个比较简单的递归实现:
/**
* Calculate and return.
* @param x
* @param n
* @return
*/
public static int calc(int x, int n){
// count the times of recursion
count ++;
// base case
if(n == 0){
return 1;
} // end if
// recurse
if(n > 0){
return x * calc(x, n - 1);
} // end if
return 0;
} // end calc
这个程序片段完成的功能是递归实现计算x的n次幂。相当于power函数的功能。笔者昨天写了两种递归、一种迭代对此功能进行测试。发现在处理类似问题上,迭代和递归的效率还是差不多的。但是有些问题比如著名的汉诺塔问题基本就是只能用递归了。
也就是在前天,学校举行的ACM网络赛有一道牛繁殖的问题(类似兔子繁殖问题),我最开始的反应也是用递归实现,而且用C在20行就解决了,代码就略了(前天忘了拷贝回来了,而且类似的代码不少),但是submit时一直不成功,原因很简单:超时了!!后来我测试一下比较大的数,还真的几十秒才出来,太大的话就干脆不出来了!!所以,用递归实现类似的计数类得问题,建议还是首选迭代吧。
好吧!到此说声晚安吧!明天早上8点还得去集训呢!!
加油加油!!!
![点击查看原始大小图片](http://dl2.iteye.com/upload/attachment/0048/9523/e201dd60-eec8-3193-9d0d-68c3f2db1d4f-thumb.jpg)
- 大小: 110.4 KB
分享到:
相关推荐
递归先序遍历二叉树: 递归中序遍历二叉树: 递归后序遍历二叉树: 非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单...
麻省理工2017深度学习公开课:递归神经网络.pdf
C语言程序设计:递归与分治策略 递归和分治策略是C语言程序设计中的两个重要概念。递归是一种算法设计技术,通过将问题分解成更小的子问题,并递归地解决这些子问题来解决原问题。分治策略是将问题分解成更小的子...
实验目的:掌握递归函数的设计与实现方法 实验原理: 递归函数的设计 实验步骤:编写程序实现教材P12例2-5 整数划分问题 问题描述:整数划分问题是将一个正整数n拆成一组数连加并等于n的形式,且这组数中的最大加数不...
05_JavaSE面试题:递归与迭代
递归函数的定义 在函数内部,可以调用其他函数。如果一个函数在内部调用自身本身,这个函数就是递归函数。 递归函数的特点 递归函数的优点是定义简单,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但...
C++语言程序设计:递归与分治策略.ppt
java基础编程:递归思想求解第5个人的年龄问题
通过分析这个zip文件中的源码,我们可以学习如何将递归的思想应用到实际问题中,以及如何有效地处理二维数据结构。同时,这个例子也展示了如何在Java中编写清晰、易于理解和维护的代码。如果你正在学习Java或数据...
2020年计算机等级VB语言核心知识点:递归过程.docx
递归算法与数据结构 递归(Recursion)是指在函数定义中调用自己本身的编程技巧。递归函数可以将复杂的问题分解成更小的子问题,直到解决最简单的子问题,从而解决整个问题。递归算法广泛应用于数据结构、算法设计...
本节我们将深入探讨生成器在递归中的应用,以标题“学学Python_49类的成员08 生成器的使用:递归”为例,结合描述中提到的文章链接,我们将讨论如何结合这两种强大的概念。 递归是一种编程技术,其中函数或方法调用...
数据结构递归ppt,有助于初学者学习!很有用。
事业单位考试计算机基础知识:递归算法之解决问题的特点.docx
在学习汇编语言的过程中,理解微机原理至关重要。汇编语言是与机器最接近的编程语言,直接对应于CPU的指令集。了解寄存器、内存模型和指令集架构可以帮助我们更好地编写高效、优化的代码。 总结来说,通过汇编语言...
递归算法简洁明了,但递归深度与树的高度相关,可能会导致栈溢出问题。 **非递归算法** 主要有两种常见方法:层次遍历(使用队列)和 Morris遍历(不使用额外空间)。 - **层次遍历**(BFS,广度优先搜索):使用...
编制一个递归下降分析程序,实现对词法分析程序所提供的单词序列的语法检查和结构分析。
通过学习“acm递归算法总结”,参赛者可以深入理解递归思想,提高解决复杂问题的能力,尤其是在面对时间限制和空间限制的ACM竞赛环境下。掌握好递归算法,对于提升编程能力,尤其是在算法设计和复杂问题求解方面具有...
Oracle 递归函数介绍 Oracle 递归函数是一种特殊的PL/SQL函数,可以用于解决复杂的树形结构查询问题。递归函数可以自我调用,以便遍历树形结构的每个节点,直到达到停止条件。 在 Oracle 中,递归函数的定义语法...
递归