一、递归和循环的关系
1、 递归的定义
顺序执行、循环和跳转是冯·诺依曼计算机体系中程序设计语言的三大基本控制结构,这三种控制结构构成了千姿百态的算法,程序,乃至整个软件世界。递归也算是一种程序控制结构,但是普遍被认为不是基本控制结构,因为递归结构在一般情况下都可以用精心设计的循环结构替换,因此可以说,递归就是一种特殊的循环结构。因为递归方法会直接或间接调用自身算法,因此是一种比迭代循环更强大的循环结构。
2、 递归和循环实现的差异
循环(迭代循环)结构通常用在线性问题的求解,比如多项式求和,为某一结果的精度进行的线性迭代等等。一个典型的循环结构通常包含四个组成部分:初始化部分,循环条件部分,循环体部分以及迭代部分。以下代码就是用循环结构求解阶乘的例子:
86/*循环算法计算小数字的阶乘, 0 <= n < 10 */
87int 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 */
101int CalcFactorial(int n)
102{
103 if(n == 0) /*最小问题的解,也就是递归终止条件*/
104 return 1;
105
106 return n * CalcFactorial(n - 1); /*递归定义*/
107}
|
从上面两个例子可以看出:递归结构算法代码结构简洁清晰,可读性强,非常符合“代码就是文档”的软件设计哲学。但是递归方法的缺点也很明显:运行效率低,对存储空间的占用也比迭代循环方法多。递归方法通过嵌套调用自身达到循环的目的,函数调用引起的参数入栈等开销会降低算法效率,同样,对存储空间的占用也体现在入栈参数以及局部变量所占用的栈空间。正因为这两点,递归方法的应用以及解题的规模都受系统任务或线程栈空间大小的影响,在一些嵌入式系统中,任务或线程的栈空间只有几千个字节,在设计算法上要慎用递归结构算法,否则很容易导致栈溢出而系统崩溃。
3、 滥用递归的一个例子
关于使用递归方法导致栈溢出的例子有很多,网上流传一个判断积偶数的例子,本人已经不记得具体内容了,只记得大致是这样的:
115/*从网上摘抄的某人写的判断积偶数的代码,使用了递归算法*/
116bool 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系统上栈空间的有趣话题,这里不再赘述。下面就是一个合理的、中规中矩的实现:
109bool IsEvenNumber(int n)
110{
111 return ((n % 2) == 0);
112}
|
二、递归还是循环?这是个问题
1、 一个简单的24点程序
下面本文将通过两个题目实例,分别给出用递归方法和循环方法的解决方案以及解题思路,便于读者更好地掌握两种方法。首先是一个简单的计算24点的问题(为了简化问题,我们假设只使用求和计算方法):
从1-9中任选四个数字(数字可以有重复),使四个数字的和刚好是24。
题目很简单,数字都是个位数,可以重复且之用加法,循环算法的核心就是使用四重循环穷举所有的数字组合,对每一个数字组合进行求和,判断是否是24。使用循环的版本可能是这个样子:
8const unsigned int NUMBER_COUNT = 4; //9
9const int NUM_MIN_VALUE = 1;
10const int NUM_MAX_VALUE = 9;
11const unsigned int FULL_NUMBER_VALUE = 24;//45;
40void 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()函数变成臭不可闻的垃圾代码。
现在看看如何用递归方法解决这个问题。递归方法的解题思路就是对题目规模进行分解,将四个数字的求和变成三个数字的求和,两个数字的求和,当最终变成一个数字时,就达到了递归终止条件。这个题目的递归解法非常优雅:
67void 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
88void 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
根据以上分析结果,逆序单链表的循环算法如下所示:
61LINK_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为头节点的单链表逆序,并返回新的头节点指针,应该是这个样子:
77LINK_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指针翻转过来。递归算法的完整代码如下:
77LINK_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}
|
循环还是递归?这是个问题。当面对一个问题的时候,不能一概认为哪种算法好,哪种不好,而是要根据问题的类型和规模作出选择。对于线性数据结构,比较适合用迭代循环方法,而对于树状数据结构,比如二叉树,递归方法则非常简洁优雅。
分享到:
相关推荐
顺序执行、循环和跳转是冯·诺依曼计算机体系中程序设计语言的三大基本控制结构,这三种控制结构构成了千姿百态的算法,程序,乃至整个软件世界。递归也算是一种程序控制结构,但是普遍被认为不是基本控制结构,因为...
【实验目的】 深入理解分治法的算法思想,应用分治法解决实际的算法问题。...表中第一列是选手编号,表中第i行和第j列(j>1)处填入第i个选手在第j天所遇到的选手。例如8个选手的日程表安排如右图所示。
循环递归算法设计 循环递归算法设计 循环递归算法设计
有关循环,递归的一些算法例子,解释,数据,字符在程序中的存储,表示。
递归算法与循环算法的分析
(1)编写求F(n)的递归算法fun1(n),(2)采用循环消除递归法fun1(n)求F(n)的值。 二是稀疏矩阵的操作,基本功能要求:稀疏矩阵采用三元组表示,求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C,并输出C。
在不失去其普遍性的前提下,可以把循环和递归分别用下列伪代码概括。 伪代码格式说明:循环采用while形式;变量不加定义;赋值用:=;条件表达式和执行的语句都写成函数的形式,圆括号内写上相关的值。其他语法方面,...
n皇后算法,,回溯,for循环嵌套递归,矩阵来存储数据
循环递归, 算法设计,PPT内容包括3.1循环与递归 3.3 算法优化基本技巧3.2 算法与数据结构 3.4 优化算法的数学模型
3、在PLC内应用存在局限性,但可以将项目上相似逻辑区域“合并同类项”,写一个包括相似性最大的函数块并配置好数据引脚,循环调用同一个函数方法去解决不同子区域的问题,进而实现整体项目的解决!
c++面试题,螺旋矩阵递归算法实现及动态内存分配
* 使用一个简单的循环,但是在很复杂的情况,算法中必须须要保留栈。本例子是简单的情况,可 * 以进一步完全消除栈。 */ ///////////////////////////////////////////////////////////////////////////// /...
循环与递归算法实验.doc
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
15个典型的递归算法的JAVA实现,求N的阶乘、欧几里德算法(求最大公约数)、斐波那契数列、汉诺塔问题、树的三种递归遍历方式、快速排序、折半查找、图的遍历、归并排序、八皇后问题(回溯、递归)、棋盘覆盖(分治,...
递归实现十进制数从高位到低位依次输出 主要是我对递归算法的初步理解后试手制作希望对你有用
通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表、单向链表、循环链表、栈的基本概念、链式堆栈、中缀表达式、队列、链式队列、串、MyString、Brute-Force算法、MySet类实现、矩阵类、递归算法、哈夫曼...
主要介绍了Python基于递归和非递归算法求两个数最大公约数、最小公倍数,涉及Python递归算法、流程循环控制进行数值运算相关操作技巧,需要的朋友可以参考下
分治依托于递归,分治是一种思想,而递归是一种手段,递归式可以刻画分治算法的时间复杂度。
排序算法 五例 排序算法一览 穷举密码算法 如何实现DES算法 入栈与出栈的所有排列可能性 三维图形的消隐算法分析 实用算法(基础算法 递推法) 数据结构:哈夫曼树的应用 数据结构学习(C++)——递归 双向链表 水波...