文档章节

算法:递归算法

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
粉丝 3
博文 158
码字总数 113941
作品 0
深圳
架构师
私信 提问
递归算法转非递归

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

u012557298
2017/12/01
0
0
递归算法经典实例小结(C#实现)

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

雲霏霏
2015/02/04
0
0
时间复杂度和空间复杂度的理解

一个算法的时间复杂度其实就是这个算法跑过的次数 eg: 这个算法执行的总次数f(n)=n^2 + 2*n; 简单来说时间复杂度就是这个函数执行的基本操作次数 你是不是会想时间复杂度为什么不用时间来衡...

triorwy
2017/12/09
0
0
python之递归

递归 特点: 递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点:...

鹏爱
2017/07/17
0
0
GIS矢量数据化简:一种改进的道格拉斯-普克算法以及C++实现

既然今天有时间,就多写几篇博文算了,也为了明天出去玩好好放松一下。 GIS领域的同志都知道,传统的道格拉斯-普克算法都是递归实现。然而有时候递归的层次太深的话会出现栈溢出的情况。在此...

长平狐
2013/12/25
171
0

没有更多内容

加载失败,请刷新页面

加载更多

微服务分布式事务实现

https://www.processon.com/view/link/5b2144d7e4b001a14d3d2d30

WALK_MAN
38分钟前
0
0
《大漠烟尘》读书笔记及读后感文章3700字

《大漠烟尘》读书笔记及读后感文章3700字: 在这个浮躁的社会里,你有多久没有好好读完一本书了? 我们总觉得自己和别人不一样,所以当看到别人身上的问题时,很少有“反求诸己”,反思自己。...

原创小博客
今天
1
0
大数据教程(9.5)用MR实现sql中的jion逻辑

上一篇博客讲解了使用jar -jar的方式来运行提交MR程序,以及通过修改YarnRunner的源码来实现MR的windows开发环境提交到集群的方式。本篇博主将分享sql中常见的join操作。 一、需求 订单数据表...

em_aaron
今天
1
0
十万个为什么之什么是resultful规范

起源 越来越多的人开始意识到,网站即软件,而且是一种新型的软件。这种"互联网软件"采用客户端/服务器模式,建立在分布式体系上,通过互联网通信,具有高延时(high latency)、高并发等特点...

尾生
今天
1
0
Terraform配置文件(Terraform configuration)

Terraform配置文件 翻译自Terraform Configuration Terraform用文本文件来描述设备、设置变量。这些文件被称为Terraform配置文件,以.tf结尾。这一部分将讲述Terraform配置文件的加载与格式。...

buddie
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部