定义:
在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
例子:
- 从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?“从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?‘从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?……’”
-
一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:“一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:‘一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到……’”
程序语言中的递归:
程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。
递归的条件:
一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
- 基线条件 base case 函数不再调用自己
- 递归条件 函数调用自己
构成递归需具备的条件:
- 子问题须与原始问题为同样的事,且更为简单;
- 不能无限制地调用本身,须有个出口,化简为非递归状况处理。
递归的缺点:
递归算法解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
栈:
实例:求阶乘
def factorial(n): if n == 1: return n else: return n*factorial(n-1) |
上例中,n==1是基线条件(base case),n $\neq$ 1是递归条件(recursive case)。
栈
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
栈是限定仅在表头进行插入和删除操作的线性表。
堆叠数据结构使用两种基本操作:推入(push)和弹出(pop):
- 推入:将数据放入堆叠的顶端(阵列形式或串列形式),堆叠顶端top指标加一。
- 弹出:将顶端数据资料输出(回传),堆叠顶端资料减一。
栈的基本特点:
- 先入后出,后入先出。
- 除头尾节点之外,每个元素有一个前驱,一个后继。
相关推荐
计算机算法设计与分析:3第三章递归.ppt
非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度: 交换二叉树的左右子树: 二叉树已左右交换。 递归先序遍历二叉树: 递归...
C语言版 数据结构与算法课程 第3章 排序算法基础(共46页).ppt C语言版 数据结构与算法课程 第4章 哈希表(共49页).ppt C语言版 数据结构与算法课程 第5章 递归算法(共77页).pptx C语言版 数据结构与算法课程 第...
计算机算法设计与分析:第三章_递归算法.ppt
.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法.net 递归算法
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
程序设计-C and C++的实现:第6章 函数和递归入门.pdf
这里的所有的markdown语法都是我在Mac...第3章:算法 第4章:数论与密码学 第5章:归纳和递归 第6章:计数 第7章:离散概率 第8章:高级计数技术 第9章:关系 第10章:图 第11章:树 第12章:布尔代数 第13章:计算模型
算法设计与分析:第2章 递归法.pdf
递归算法详解递归算法详解递归算法详解递归算法详解
第6章 递归 什么是递归 递归算法举例 线性表下递归算法设计 递归算法性能分析 递归回溯法 常见算法设计模式
数据结构课件:05 第六章 递归.ppt
小小学习,C语言数据结构,中序遍历二叉树非递归算法
快速选择非递归与递归算法实现
递归算法思想和实现 快速理解递归的设计思想
5!递归算法和非递归算法,面试专用,适合新手
acm递归算法总结acm递归算法总结!!!!!!!!!!!!!!!!!!!!!!!
算法设计与分析:第02章 递归与分治策略.ppt