文档章节

算法:递归算法

wiitht
 wiitht
发布于 2017/05/12 17:28
字数 1426
阅读 4
收藏 0

    程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

递归,就是在运行的过程中调用自己。

构成递归需具备的条件:

1. 子问题须与原始问题为同样的事,且更为简单;

2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

数学计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。

栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程,称做递归过程。递归是程序设计中一个强有力的工具。

栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时,系统每次向栈中压入一个对象,然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时,最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。

递归之所以能实现,是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝,这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础,是使得递归成为可能。假定某个调用函数调用了一个被调用函数,再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归,因为它发生在调用函数的当前执行过程运行完毕之前。而且,因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量,原先的参数和变量将不受影响,所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。
     程序员需保证递归函数不会随意改变静态变量和全局变量的值,以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程,并且返回到顶层。

public static void recursion(int n){
   if (n==0){
     return;
   }
   if (n > 0) {
     n --;
     recursion(n);
   } 
   System.out.print(" " + n);
}
输出结果:
0 1 2 3 4 5 6 7 8 9

public static void recursion(int n){
   if (n==0){
     return;
   }
   if (n > 0) {
     n --;
     System.out.print(" " + n);
     recursion(n);
   } 
   
}
输出结果:
9 8 7 6 5 4 3 2 1 0

很明显将打印语句放在不同的位置,输出的结果顺序也不一样;递归的在调用的过程中是做了一系列的过程拷贝的,而这些拷贝,本身又是存在于栈中,栈的特点是先进后出,所以当调用准备释放的时候,在recursion递归调用之后的语句拷贝将会逐步释放。

当一个函数(调用者)调用另一个函数(被调用者)时,运行时系统将把调用者的所有实参和返回地址压入到栈中,栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时,系统把被调用者的自变量压入到栈中,并把栈指针再向下移,以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后,被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作,栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针,以他为参考,用正或负的偏移值来访问栈中的变量。当被调用者准备返回时,系统弹出栈中所有的自变量,这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回,系统从栈中弹出返回地址,调用者就可以继续执行了。当调用者继续执行时,系统还将从栈中弹出调用者的实参,于是栈指针回到了调用发生前的位置。
    

http://blog.csdn.net/u010697982/article/details/45875913 

http://blog.csdn.net/qiujunchao/article/details/4373321

本文转载自:

共有 人打赏支持
wiitht
粉丝 2
博文 158
码字总数 113789
作品 0
深圳
架构师
递归算法转非递归

将递归算法转换为非递归算法有两种方法,一种是直接求值,不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转...

u012557298
2017/12/01
0
0
算法的时间复杂度与空间复杂度分析

算法的时间性能分析 1.算法消耗的时间 一个算法的执行时间是指算法中所有语句执行时间的总和。每条语句的执行时间等于该条语句的执行次数乘以执行一次所需实际时间。 由于语句的执行要由源程...

xy294636185
05/25
0
0
递归算法经典实例小结(C#实现)

一 、递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。   递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问...

雲霏霏
2015/02/04
0
0
简单图像填充算法

填充算法 递归 private void fillsearch(Bitmap bmp, int x, int y, byte[,] flag,int num) { //向左 如果为1返回 如果不是1 计算当前值 如果不在范围内设为1返回 并且向下递归 if (Math.Abs...

魂祭心
2015/12/20
67
0
java递归算法实现

Fibonacci数列:1,1,2,3,5,8,13…… public classFab { public static void main(String args[]){ } private static int fab(int index){ } } 程序分析: 这个实例是非常经典的实例,主......

动听的椰子
2016/03/01
42
0

没有更多内容

加载失败,请刷新页面

加载更多

关于编程,你的练习是不是有效的?

最近由于工作及Solution项目的影响,我在重新学习DDD和领域建模的一些知识。然后,我突然就想到了这个问题,以及我是怎么做的? 对于我来说,提升技能的项目会有四种: 纯兴趣驱动的项目。即...

问题终结者
29分钟前
1
0
打开eclipse出现an error has occurred see the log file

解决方法: 1,打开eclipse安装目录下的eclipse.ini文件; 2,打开的文本文件最后添加一行 --add-modules=ALL-SYSTEM 3,保存重新打开Eclipse。...

任梁荣
昨天
4
0
搞定Northwind示例数据库,无论哪个版本的SQLServer都受用

Northwind数据库 从这里可以找到突破口: http://social.msdn.microsoft.com/Forums/zh-CN/Vsexpressvb/thread/8490a1c6-9018-40c9-aafb-df9f79d29cde 下面是MSDN: http://msdn2.microsoft......

QQZZFT
昨天
1
0
mysql主从同步,安装配置操作

准备 两台mysql服务,我这里准备了如下: 主库:192.168.176.128 从库:192.168.176.131 如何在Linux上安装mysql服务,请看https://blog.csdn.net/qq_18860653/article/details/80250499 操作...

小致dad
昨天
4
0
Redis的“死键”问题

大规模的数据库存储系统中,数据的生命周期管理是很有必要的;从业务角度发现过期数据,数据归档和数据碎片整理等。以MySQL为例,1个运行很久的TB级MySQL实例中,极有可能数百GB的数据,对业...

IT--小哥
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部