1、 递归的定义
顺序执行、循环和跳转是冯·诺依曼计算机体系中程序设计语言的三大基本控制结构,这三种控制结构构成了千姿百态的算法,程序,乃至整个软件世界。递归也算是一种程序控制结构,但是普遍被认为不是基本控制结构,因为递归结构在一般情况下都可以用精心设计的循环结构替换,因此可以说,递归就是一种特殊的循环结构。因为递归方法会直接或间接调用自身算法,因此是一种比迭代循环更强大的循环结构。
2、 递归和循环实现的差异
循环(迭代循环)结构通常用在线性问题的求解,比如多项式求和,为某一结果的精度进行的线性迭代等等。一个典型的循环结构通常包含四个组成部分:初始化部分,循环条件部分,循环体部分以及迭代部分。以下代码就是用循环结构求解阶乘的例子:
86 /*循环算法计算小数字的阶乘, 0 <= n < 10 */ 87 int CalcFactorial(int n) 88 { 89 int result = 1; 90 91 int i; 92 for(i = 1; i <= n; i++) 93 { 94 result = result * i; 95 } 96 97 return result; 98 } |
递归方法通常分为两个部分:递归关系和递归终止条件(最小问题的解)。递归方法的关键是确定递归定义和递归终止条件,递归定义就是对问题分解,是指向递归终止条件转化的规则,而递归终止条件通常就是得出最小问题的解。递归结构与人类解决问题的方式类似,算法简洁且易于理解,用较少的步骤就能描述解题的全过程。递归方法的结构中还隐含了一个步骤,就是“回溯”,对于需要“先进后出”结构进行操作时,使用递归方法会更高效。以下代码就是用递归方法求解阶乘的例子:
100 /*递归算法计算小数字的阶乘, 0 <= n < 10 */ 101 int CalcFactorial(int n) 102 { 103 if(n == 0) /*最小问题的解,也就是递归终止条件*/ 104 return 1; 105 106 return n * CalcFactorial(n - 1); /*递归定义*/ 107 } |
从上面两个例子可以看出:递归结构算法代码结构简洁清晰,可读性强,非常符合“代码就是文档”的软件设计哲学。但是递归方法的缺点也很明显:运行效率低,对存储空间的占用也比迭代循环方法多。递归方法通过嵌套调用自身达到循环的目的,函数调用引起的参数入栈等开销会降低算法效率,同样,对存储空间的占用也体现在入栈参数以及局部变量所占用的栈空间。正因为这两点,递归方法的应用以及解题的规模都受系统任务或线程栈空间大小的影响,在一些嵌入式系统中,任务或线程的栈空间只有几千个字节,在设计算法上要慎用递归结构算法,否则很容易导致栈溢出而系统崩溃。
3、 滥用递归的一个例子
关于使用递归方法导致栈溢出的例子有很多,网上流传一个判断积偶数的例子,本人已经不记得具体内容了,只记得大致是这样的:
115 /*从网上摘抄的某人写的判断积偶数的代码,使用了递归算法*/ 116 bool IsEvenNumber(int n) 117 { 118 if(n >= 2) 119 return IsEvenNumber(n - 2); 120 else 121 { 122 if(n == 0) 123 return true; 124 else 125 return false; 126 } 127 } |
据说这个例子是某个系统中真是存在的代码,它经受住了最初的测试并被发布出去,当用户的数据大到一定的规模时崩溃了。本人在Windows系统上做过测试,当n超过12000的时候就会导致栈溢出,本系列的下一篇文章,会有一个有关Windows系统上栈空间的有趣话题,这里不再赘述。下面就是一个合理的、中规中矩的实现:
109 bool IsEvenNumber(int n) 110 { 111 return ((n % 2) == 0); 112 } |
二、递归还是循环?这是个问题
1、 一个简单的24点程序
下面本文将通过两个题目实例,分别给出用递归方法和循环方法的解决方案以及解题思路,便于读者更好地掌握两种方法。首先是一个简单的计算24点的问题(为了简化问题,我们假设只使用求和计算方法):
从1-9中任选四个数字(数字可以有重复),使四个数字的和刚好是24。
题目很简单,数字都是个位数,可以重复且之用加法,循环算法的核心就是使用四重循环穷举所有的数字组合,对每一个数字组合进行求和,判断是否是24。使用循环的版本可能是这个样子:
8 const unsigned int NUMBER_COUNT = 4; //9 9 const int NUM_MIN_VALUE = 1; 10 const int NUM_MAX_VALUE = 9; 11 const unsigned int FULL_NUMBER_VALUE = 24;//45; 40 void PrintAllSResult(void) 41 { 42 int i,j,k,l; 43 int numbers[NUMBER_COUNT] = { 0 }; 44 45 for(i = NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++) 46 { 47 numbers[0] = i; /*确定第一个数字*/ 48 for(j = NUM_MIN_VALUE; j <= NUM_MAX_VALUE; j++) 49 { 50 numbers[1] = j; /*确定第二个数字*/ 51 for(k = NUM_MIN_VALUE; k <= NUM_MAX_VALUE; k++) 52 { 53 numbers[2] = k; /*确定第三个数字*/ 54 for(l = NUM_MIN_VALUE; l <= NUM_MAX_VALUE; l++) 55 { 56 numbers[3] = l; /*确定第四个数字*/ 57 if(CalcNumbersSum(numbers, NUMBER_COUNT) ==FULL_NUMBER_VALUE) 58 { 59 PrintNumbers(numbers, NUMBER_COUNT); 60 } 61 } 62 } 63 } 64 } 65 } |
这个PrintAllSResult()函数看起来中规中矩,但是本人的编码习惯很少在一个函数中使用超过两重的循环,更何况,如果题目修改一下,改成9个数字求和是45的组合序列,就要使用9重循环,这将使PrintAllSResult()函数变成臭不可闻的垃圾代码。
现在看看如何用递归方法解决这个问题。递归方法的解题思路就是对题目规模进行分解,将四个数字的求和变成三个数字的求和,两个数字的求和,当最终变成一个数字时,就达到了递归终止条件。这个题目的递归解法非常优雅:
67 void EnumNumbers(int *numbers, int level, int total) 68 { 69 int i; 70 71 for(i = NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++) 72 { 73 numbers[level] = i; 74 if(level == (NUMBER_COUNT - 1)) 75 { 76 if(i == total) 77 { 78 PrintNumbers(numbers, NUMBER_COUNT); 79 } 80 } 81 else 82 { 83 EnumNumbers(numbers, level + 1, total - i); 84 } 85 } 86 } 87 88 void PrintAllSResult2(void) 89 { 90 int numbers[NUMBER_COUNT] = { 0 }; 91 92 EnumNumbers(numbers, 0, FULL_NUMBER_VALUE); 93 } |
如果题目改成“9个数字求和是45的组合序列”,只需将NUMBER_COUNT的值改成9,FULL_NUMBER_VALUE的值改成45即可,算法主体部分不需做任何修改。
2、 单链表逆序
第二个题目是很经典的“单链表逆序”问题。很多公司的面试题库中都有这道题,有的公司明确题目要求不能使用额外的节点存储空间,有的没有明确说明,但是如果面试者使用了额外的节点存储空间做中转,会得到一个比较低的分数。如何在不使用额外存储节点的情况下使一个单链表的所有节点逆序?我们先用迭代循环的思想来分析这个问题,链表的初始状态如图(1)所示:
图(1)初始状态
初始状态,prev是NULL,head指向当前的头节点A,next指向A节点的下一个节点B。首先从A节点开始逆序,将A节点的next指针指向prev,因为prev的当前值是NULL,所以A节点就从链表中脱离出来了,然后移动head和next指针,使它们分别指向B节点和B的下一个节点C(因为当前的next已经指向B节点了,因此修改A节点的next指针不会导致链表丢失)。逆向节点A之后,链表的状态如图(2)所示:
图(2)经过第一次迭代后的状态
从图(1)的初始状态到图(2)状态共做了四个操作,这四个操作的伪代码如下:
head->next = prev;
prev = head;
head = next;
next = head->next;
这四行伪代码就是循环算法的迭代体了,现在用这个迭代体对图(2)的状态再进行一轮迭代,就得到了图(3)的状态:
图(3)经过第二次迭代后的状态
那么循环终止条件呢?现在对图(3)的状态再迭代一次得到图(4)的状态:
图(4)经过第三次迭代后的状态
此时可以看出,在图(4)的基础上再进行一次迭代就可以完成链表的逆序,因此循环迭代的终止条件就是当前的head指针是NULL。
现在来总结一下,循环的初始条件是:
prev = NULL;
循环迭代体是:
next = head->next;
head->next = prev;
prev = head;
head = next;
循环终止条件是:
head == NULL
根据以上分析结果,逆序单链表的循环算法如下所示:
61 LINK_NODE *ReverseLink(LINK_NODE *head) 62 { 63 LINK_NODE *next; 64 LINK_NODE *prev = NULL; 65 66 while(head != NULL) 67 { 68 next = head->next; 69 head->next = prev; 70 prev = head; 71 head = next; 72 } 73 74 return prev; 75 } |
现在,我们用递归的思想来分析这个问题。先假设有这样一个函数,可以将以head为头节点的单链表逆序,并返回新的头节点指针,应该是这个样子:
77 LINK_NODE *ReverseLink2(LINK_NODE *head) |
现在利用ReverseLink2()对问题进行求解,将链表分为当前表头节点和其余节点,递归的思想就是,先将当前的表头节点从链表中拆出来,然后对剩余的节点进行逆序,最后将当前的表头节点连接到新链表的尾部。第一次递归调用ReverseLink2(head->next)函数时的状态如图(5)所示:
图(5)第一次递归状态图
这里边的关键点是头节点head的下一个节点head->next将是逆序后的新链表的尾节点,也就是说,被摘除的头接点head需要被连接到head->next才能完成整个链表的逆序,递归算法的核心就是一下几行代码:
84 newHead = ReverseLink2(head->next); /*递归部分*/ 85 head->next->next = head; /*回朔部分*/ 86 head->next = NULL; |
现在顺着这个思路再进行一次递归,就得到第二次递归的状态图:
图(6)第二次递归状态图
再进行一次递归分析,就能清楚地看到递归终止条件了:
图(7)第三次递归状态图
递归终止条件就是链表只剩一个节点时直接返回这个节点的指针。可以看出这个算法的核心其实是在回朔部分,递归的目的是遍历到链表的尾节点,然后通过逐级回朔将节点的next指针翻转过来。递归算法的完整代码如下:
77 LINK_NODE *ReverseLink2(LINK_NODE *head) 78 { 79 LINK_NODE *newHead; 80 81 if((head == NULL) || (head->next == NULL)) 82 return head; 83 84 newHead = ReverseLink2(head->next); /*递归部分*/ 85 head->next->next = head; /*回朔部分*/ 86 head->next = NULL; 87 88 return newHead; 89 } |
循环还是递归?这是个问题。当面对一个问题的时候,不能一概认为哪种算法好,哪种不好,而是要根据问题的类型和规模作出选择。对于线性数据结构,比较适合用迭代循环方法,而对于树状数据结构,比如二叉树,递归方法则非常简洁优雅。
原文地址 <a href = "http://blog.csdn.net/orbit/article/details/7585756 "> http://blog.csdn.net/orbit/article/details/7585756 </a>
相关推荐
当删除一个部门时,需要递归删除该部门下的所有子部门,以避免出现部门之间的循环引用。该功能使用Java语言实现,具有良好的可扩展性和可维护性。 4. 部门信息查询接口设计 在Java递归树型结构通用数据库中,提供...
1、培养独立思考算法的能力,特别是递归时,用到的是数学中的数列,找到整个递归的最先出栈的函数,以及数列的第n项与第n-1项的关系就能用递归解决问题; 2、通过试数来推算自己的程序逻辑是否有beg,并找出修复之...
我们制定了一种方法,以递归定义系数的极点总和形式找到高阶递归关系的亚纯解。 给出了该技术应用的几个明确的例子。... 这些正是基于尺寸递归关系和分析性(DRA方法)的多循环计算方法的应用所需要的属性。
递归两要素:递归关系和递归边界(终止条件),递归关系确定了迭代的层次结构,需要深入了解并分解问题;终止条件保证了程序的有穷性。 递归的应用有很多,常见的包括:阶乘运算、斐波那契数列、汉诺塔、数的遍历,...
2、找这一次和上一次的关系 3、假设当前函数已经能用,调用自身计算上一次的结果再求出本次的结果 下面我们通过两段代码简单看一下递归和非递归的区别: 输入一个大于等于1的数,求1到n的和! # 普通函数方法 ...
2、找出这一次和上一次关系 3、假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+…+n的数和# 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,...
长期短期记忆网络(通常被称为“LSTM”)是一种特殊的RNN,能够学习长期的依赖关系 明确设计LSTM是为了避免长期依赖性问题。记住长时间的信息实际上是他们的默认行为,而不是他们难以学习的东西!所有经常性的神经...
2. 长短期记忆网络(Long Short-Term Memory,LSTM):一种改进的循环神经网络结构,引入了细胞状态和门控机制,能够更好地处理长期依赖关系。 3. 门控递归单元网络(Gated Recurrent Unit,GRU):一种高速的循环...
递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1、写出临界条件 2、找出这一次和上一次关系 3、假设当前函数已经能用,调用自身计算上一次的结果,再求出...
其核心就是for循环里面的递归,在递归调用之前“做选择”,在递归调用之后“撤销选择”。 什么叫撤销选择?这个框架的底层原理是什么呢?下面我们就通过全排列问题解开之前的疑惑,一探究竟吧!!! ——————...
RNN 的典型特征是循环连接,使得 RNN 能够根据历史输入和当前输入更新当前状态。RNN 的计算方法可以用公式表示: ot = g(Vht) ht = f(Uxt + Wht-1) 其中,g 和 f 均为激励函数。 LSTM 是 RNN 的一种变体,能够更...
因此,这些网络在某些情况下优于它们的卷积和递归对,因为它们能够处理图像序列,并且在本工作的特殊情况下,可以处理经过卷积软化和递归处理的监测数据的时间序列。本工作的总体目标是基于卷积递归神经网络(ConvRNN...
在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在...当所有的金片都从梵天穿好的那根针上移到另外一概针上时,世界就将在一声霹雳中消灭,梵塔、庙宇和众生都将同归于尽。故汉诺塔问题又被称为“世界末日问题。”
在摄动理论中,我们分别将1 / 6-BPS和1 / 2-BPS Wilson循环的期望值分别计算为三环和两环,通过递归关系处理多重绕组的组合。 对于1 / 6-BPS Wilson循环,我们在通用框架中执行计算,在框架1中我们发现与定位结果...
由于预测分析和递归子程序都是自顶向下的分析方法,这里给出无回溯的和无左公因子的文法。无左递归和无左公因子的BNF如下: <程序>→<程序首部><分程序>. <程序首部>→PROGRAM 标识符; <分程序>→<常量说明...
它使用递归关系和模块化算法来生成整数数组,然后对它们进行颜色编码。 用户控制循环关系,模数和颜色编码规则的参数。 结果立即反映在屏幕上的简化预览中。 用户可以将图案的高分辨率图像保存到他们的计算机。 ...
介绍依赖树是(非常)简单的插件,它显示了 Eclipse 中给定 Java 项目的递归依赖关系(和依赖循环)。 将(直接或间接)所需项目的列表写入文本文件。 这个插件可以帮助解决项目的循环依赖。 您可能想要使用它,因为...
23. 一个问题用递归方法解决,必须满足两个条件:递归关系式、递归出口。知识点:递归算法的使用和限制。 24. 在巡线中某时刻,机器人最后连续测量的光值差分别为(5、3、1),理论上我们可以预计下次机器人测量的光...
深密封 递归调用函数和对象上的Object.seal。 基于子堆栈的模块。 deep-seal具有可选的附加支持,用于检查循环依赖关系,我发现其他模块陷入无限循环并引发类型错误。 您可以在第二个参数中传递true ,以在实际密封...
我们提出了一种新的递归控制循环网络(RCRN),该网络在许多NLP任务上都显示了对堆叠式BiLSTM和BiLSTM的改进。 根据定制的cuda优化内核,该存储库包含RCRN的Tensorflow模型文件。 如果有时间(已经有大量积压的...