递归函数与非递归的转化

格式：ppt
大小：661.00 KB
文档页数：6

下载文档原格式

/ 6

2014年12月中南大学网络教育课程考试：算法分析与设计作业参考答案

《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。

2.程序：程序是算法用某种程序设计语言的具体实现。

二、简答题：1.算法需要满足哪些性质？简述之。

答：算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入。

（2）输出：算法产生至少一个量作为输出。

（3）确定性：组成算法的每条指令清晰、无歧义。

（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

答：将递归算法转化为非递归算法的方法主要有：（1）采用一个用户定义的栈来模拟系统的递归调用工作栈。

该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

（2）用递推来实现递归函数。

（3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下：for i ←1 to n-1 do for j ←1 to n-i do if a[j]<a[j+1] then 交换a[j]、a[j+1]；分析该算法的时间复杂性。

答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n 的关系。

（1）设比较一次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。

面向对象的三个基本特征和概念

面向对象的三个基本特征（讲解）面向对象的三个基本特征是：封装、继承、多态。

封装封装最好理解了。

封装是面向对象的特征之一，是对象和类概念的主要特性。

封装，也就是把客观事物封装成抽象的类，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏。

继承面向对象编程 (OOP) 语言的一个主要功能就是“继承”。

继承是指这样一种能力：它可以使用现有类的所有功能，并在无需重新编写原来的类的情况下对这些功能进行扩展。

通过继承创建的新类称为“子类”或“派生类”。

被继承的类称为“基类”、“父类”或“超类”。

继承的过程，就是从一般到特殊的过程。

要实现继承，可以通过“继承”（Inheritance）和“组合”（Composition）来实现。

在某些 OOP 语言中，一个子类可以继承多个基类。

但是一般情况下，一个子类只能有一个基类，要实现多重继承，可以通过多级继承来实现。

继承概念的实现方式有三类：实现继承、接口继承和可视继承。

实现继承是指使用基类的属性和方法而无需额外编码的能力；接口继承是指仅使用属性和方法的名称、但是子类必须提供实现的能力；可视继承是指子窗体（类）使用基窗体（类）的外观和实现代码的能力。

在考虑使用继承时，有一点需要注意，那就是两个类之间的关系应该是“属于”关系。

例如，Employee 是一个人，Manager 也是一个人，因此这两个类都可以继承 Person 类。

但是 Leg 类却不能继承 Person 类，因为腿并不是一个人。

抽象类仅定义将由子类创建的一般属性和方法，创建抽象类时，请使用关键字 Interface 而不是 Class。

OO开发范式大致为：划分对象→抽象类→将类组织成为层次化结构(继承和合成) →用类与实例进行设计和实现几个阶段。

多态多态性（polymorphisn）是允许你将父对象设置成为和一个或更多的他的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。

递归算法向非递归转换的一般规则

维普资讯
科技信息
０计算机与信息技术０
ＳＩＮＥＩＦＲＴＯＣＥＣＯＭＡＩＮＮ
２０年０６
第ｌ期ｌ
递归算法向非递归转换的一般规则
李红字
（尔滨师范大学阿城学院计算机与信息技术系黑龙江阿城哈
１００）５３１
摘要：归程序结构简单、递清晰，可读性好，易于验证其正确性。浪费空问且执行效率低。因此，且但有时需要把递归算法转换成非递归算法。本文培出了一种根据递归调用的内部实现原理把递归算法向非递归转换的一般规则。最后，明非递归化应谊注意的一些问题。说
关键பைடு நூலகம்词：归；归算法；递递非递归算法；栈堆
ｖｉｏｔｄｒｉｅｏｐｓｒｅ（ｔｅｔｄｏＢｒ）递归是一个重要的课题。在计算机科学和数学领域中，从理论到｛ｆ（ｉ０实践，都得到广泛的应用。在计算机科学中为递归下的定义是：若一个｛ｏｔｒｅ（＞ｃｉ）ｐｓｄｒ－ｌｌ；ｏｔｈｄ过程直接地或间接地调用自己，称这个过程是递归的过程。数学上则ｐｓｒｅ（＞ｃｉ）ｏｔｄｒ－ｒｈｌ；ｏｔｄ常用的阶乘函数、幂指数、级数、ｉｏａｃ数列、＝项式系数、组合Ｆｂｎｃｉｖｓｅｔ＞ａａ；ｉｔ（ｄｔ）ｉ－Ｃ勒让德多项式等。们的定义和计算都是递归的：据结构中的ｍ、它数】树、二叉树和广义表也是通过递归方式加以定义的。由于其本身固有｝的递归性质，而关于它们许多问题的算法均可以采用递归技术加以因转换程序如下：实现；有一些复杂的问题用递归解很简单，汉诺塔问题、宫的求还如迷ｖｉｏｔｒｅ（ｉｅｏｄｐｓｄｒｔｅｔｏＢｒ）解等等。｛解决递归问题的算法称为递归算法。归算法的本质是按分而治递Ｉｉｔｃ（）ｐｔ／则１ｎｔａｋＳ；－；／Ｓ规之算法的思想，把一・个较复杂问盾的处理归结为较简单问题的处理，Ｅ：０／则２／规并逐步把它归结为最简单情况的处理，而解决问题。递归算法的执从ｉｐｆ）（／则５／规行过程可分为自上而下的回推和白底而上的递推两个阶段。具体实在｛ｕｔ，Ｌ）／则３ｐｓ（Ｐ，１；／Ｓ规现时，是借助系统提供的栈空间来完成的。ｐｐ＞ｃｉ；／则３＝一１ｈｌｄ／规利用递归编写出来的程序，构清晰．读性好，且它的正确性结可而ｇｔ０ｏｏＥ；，则３，规容易得到证明。然而，实际应用时也存在一些问盾。要表现在以下在主Ｌ：Ｉ／则３／规Ｐｓ（，Ｌ），则３ｕｈＳＰ，２；，规几方面：一，第它需要不断调用自身，至使程序运行的效率很低。因此ｐｐ＞ｃｉ；，则３＝－ｒｈｌ，ｄ规在希望节省存储空间和追求执行效率的情况下。人们更希望使用非递归方式求解的算法程序；二，些高级程序设计语言没有提供递归第有ｇｔ０ｏＥ；ｏ，则３，规的机制和手段，对于某些具有递归性质的问题．必须使用非递归方式Ｌ：２，则３，规解决；三．究递归算法的非递归实现有助于透彻理解递归机制．第研而Ｖｉｔ（一ｄｔ）／则５ｓｅｐ＞ａａ规ｉ；／这种理解是熟练掌握递归程序技能的必要前提。下面本文主要根据递】归内部实现原理给出・非递归算法实现的规则。种ｉＳａｋｍｐｙｓ／则４ｆｔＥｔ）／ｃ（）规｛ｏ（，，）ｐｐＳＰｘ；，则４，规１递归算法向非递归转化的一般规则．１１递归算法转换成非递归算法完全模拟了递归函数的系统执．把ｇｔｏｏｘ：／则４／规行过程。这样构造的非递归算法通常语句较多．但因有固定方法可循。】故在实际软件设计中也经常他用。具体转换规则如下：】（）始化栈Ｓ１初。在构造程序的流程图时，到多个返回地址时。用分支结构实遇要（）２给每个递归函数的人口分别标以不同的标号（如从ＥＯ至Ｅ）现（或ｓｉｈｎ，ｉｗｔ语句）本程序流程图如下（１：ｆｃ，图）并在每个返回处设立一个标号 “（≥ １。ｉ）（）３将每个递归函数中的每个递归调用转化为如下操作。ａ保留现场；辟栈顶存储空间。调用层中的局部变量、式参．开将形数与返回地址保存在栈中（外层调用不必考虑）最；ｂ准备数据：．为被调用子程序准备所需的参数．即计算实在参数的值，赋给对应的形参：并ｃ转入相应的进归函数执行（．即如果被调用函数为Ｅ．则ｇｔｉｏｏ

函数的递归调用

函数的递归调用1.递归基本概念所谓递归，简而言之就是应用程序自身调用自身，以实现层次数据结构的查询和访问。

递归的使用可以使代码更简洁清晰，可读性更好。

但由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多，而且，如果递归深度太大，可能系统资源会不够用。

从理论上说，所有的递归函数都可以转换为迭代函数，反之亦然，然而代价通常都是比较高的。

但从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。

这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归定义及其简单，但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都变得不现实。

因而可以从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代。

2.C语言中的函数可以递归调用可以直接（简单递归）或间接（间接递归）地自己调自己。

这里我们只简单的谈谈直接递归。

采用递归方法来解决问题，必须符合以下三个条件：（1）可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。

说明：解决问题的方法相同，调用函数的参数每次不同（有规律的递增或递减），如果没有规律也就不能适用递归调用。

（2）可以应用这个转化过程使问题得到解决。

说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题。

（3）必定要有一个明确的结束递归的条件。

说明：一定要能够在适当的地方结束递归调用。

不然可能导致系统崩溃。

3.递归实例下面用一个实例来说明递归调用。

使用递归的方法求n!当n>1时，求n!的问题可以转化为n*(n-1)!的新问题。

比如n=5：第一部分：5*4*3*2*1 n*(n-1)!第二部分：4*3*2*1 (n-1)*(n-2)!第三部分：3*2*1 (n-2)(n-3)!第四部分：2*1 (n-3)(n-4)!第五部分：1 （n-5）! 5-5=0，得到值1，结束递归。

算法分析与设计复习题及参考答案

《算法分析与设计》课程复习资料一、名词解释：1.算法2.程序3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。

2.简述回溯法解题的主要步骤。

3.简述动态规划算法求解的基本要素。

4.简述回溯法的基本思想。

5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

6.简要分析分支限界法与回溯法的异同。

7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？ 8.贪心算法求解的问题主要具有哪些性质？简述之。

9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。

10.简述分析贪心算法与动态规划算法的异同。

三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。

2.按要求完成以下关于排序和查找的问题。

①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。

②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。

③给出上述算法的递归算法。

④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。

3.已知1()*()i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。

4.根据分枝限界算法基本过程,求解0-1背包问题。

已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。

递归算法修改为非递归算法

递归算法修改为非递归算法1.引言1.1 概述递归算法是一种常见的计算方法，它通过将大问题拆分成一个或多个相似的子问题来解决。

递归算法通常通过不断调用自身来处理这些子问题，直到达到基本情况时停止递归。

递归算法的设计具有简洁、优雅的特点，并在某些情况下能够提供高效的解决方案。

然而，递归算法也存在一些局限性。

首先，递归调用会带来额外的函数调用开销，可能会导致程序运行速度较慢。

其次，递归算法对于大规模问题的解决可能会导致堆栈溢出的问题，因为每一次递归调用都需要在内存中保存一些信息。

为了克服递归算法的局限性，我们可以将其修改为非递归算法。

非递归算法使用迭代的方式来解决问题，通过使用循环结构来代替递归调用，从而降低了函数调用的开销。

此外，非递归算法更加直观易懂，可以减少程序的复杂性。

本文将探讨递归算法修改为非递归算法的必要性和优势，并通过具体的例子和算法讲解，详细介绍如何将递归算法转化为非递归算法的思路和方法。

通过对比和分析，我们将展示非递归算法在某些情况下的效率和可行性，以及它在解决问题时的优势和不足。

在接下来的章节中，我们将首先介绍递归算法的特点，包括递归调用和基本情况的判断。

然后，我们将讨论非递归算法的优势，包括降低函数调用开销和提高程序运行效率的能力。

最后，我们将总结递归算法的局限性，强调修改为非递归算法的必要性。

1.2 文章结构本文分为引言、正文和结论三个部分。

在引言部分，我们将概述本文的主题和目的，并介绍文章的结构。

在正文部分，我们将首先探讨递归算法的特点，包括递归算法的定义、实现方式和应用场景等。

然后我们将分析非递归算法的优势，包括非递归算法相对于递归算法的效率、可读性和内存消耗等方面的优势。

接下来，在结论部分，我们将讨论递归算法的局限性，包括递归算法在处理大规模数据时存在的问题和栈溢出的风险等。

最后，我们将强调修改为非递归算法的必要性，以解决递归算法的局限性，并总结本文的主要观点和结论。

通过以上结构，我们将全面而系统地探讨递归算法修改为非递归算法的背景、原因和优势，以及非递归算法在解决问题中的应用价值。

【分析】算法分析与设计作业参考答案

【关键字】分析《算法分析与设计》作业参考答案作业一一、名词解释：1.递归算法：直接或间接地调用自身的算法称为递归算法。

2.程序：程序是算法用某种程序设计语言的具体实现。

2、简答题：1.算法需要满足哪些性质？简述之。

算法是若干指令的有穷序列，满足性质：1）输入：有零个或多个外部量作为算法的输入。

2）输出：算法产生至少一个量作为输出。

3）确定性：组成算法的每条指令清晰、无歧义。

4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

分析分治法能解决的问题主要具有如下特征：1）该问题的规模缩小到一定的程度就可以容易地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）利用该问题分解出的子问题的解可以合并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。

将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。

该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。

2）用递推来实现递归函数。

3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。

后两种方法在时空复杂度上均有较大改善，但其适用范围有限。

三、算法编写及算法应用分析题：1.冒泡排序算法的基本运算如下：for i ←1 to n-1 dofor j ←1 to n-i doif a[j]<a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。

解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。

1）设比较一次花时间1；2）内循环次数为：n-i次,（i=1,…n），花时间为：3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。

递归算法

if( knap( m-m[n],n-1 )) return true;
return knap(m,n-1); }
3.递归算法设计
递归算法
算法设计和分析
递归算法
Hanoi塔问题
汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。游戏的装置如图所示（图上以3个金片例），底座上有三根金的针，第一根针上放着从大到小64个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能
建立标号：分别在过程的第一条可执行语句处、每个递归调
用处建立标号，依次为：L0,L1,L2,……，做为入口地址和返回地址
消去递归调用：局部变量、形参、返回地址入栈,形式参数赋值，goto语句到L0
修改函数的返回部分：
• 用户栈为空，返回 • 返回值保存到全局变量中，同时将引用参数赋给栈顶的相应变量
{
CStack<int> stack;
int retvalue,retaddr;
int res ;
L0:
if( a < b )
{
res = GCD(b,a);
L1:
;
}
else if( b == 0 )
{
res = a;
}
else
{
res = GCD(b,a%b);
L2:
;
}
return res; }
}
修改标号L1处的递归调用
算法设计和分析
递归算法
else {
//res = GCD(b,a%b); //保护现场
stack.Push(a); stack.Push(b); stack.Push(res); stack.Push(2); //返回地址 stack.Push(b); stack.Push(a%b); //设置函数的调用参数 goto L0; L2: res = retvalue; //返回值放在全局变量里 }

递归算法转换为非递归算法

递归算法转换为非递归算法想象一下，递归就像是你的好朋友，老是在你耳边叨叨，告诉你：“再来一次，再来一次。

”而非递归就像是那个实在的家伙，给你一份清晰的计划，告诉你该干嘛。

用非递归的方式，咱们就能更好地控制进度，不会再像在黑暗中摸索，而是一步步地稳稳前进。

说到这里，有的人可能会问：“非递归的难度是不是太高了？”其实呢，非递归并没有想象中那么复杂，特别是如果你能掌握一些基本的技巧，就像玩拼图一样，轻松上手。

举个例子，大家都知道计算斐波那契数列吧。

那种用递归的方式计算，简直像在爬一座高山，一级一级上去，最后发现自己爬了个寂寞，特别是数字一多，简直就是给自己挖坑。

非递归的方法其实就是把这个过程变得更直白，像是在教你怎么把山坡变成一条平坦的大路。

我们可以用一个简单的循环来实现，拿着一张小纸条，把每一步都写下来。

随着每一轮的循环，数据就一点点填满，直到达成目标。

就像煮面一样，慢慢煮，耐心等待，最后面条总会熟透的。

再说个有趣的事儿，遍历树结构的时候，递归的方法就像你在给小朋友讲故事，每讲完一层就得回到上一层，像是在玩捉迷藏，兜兜转转。

可是，非递归就不一样了，咱们可以用一个栈，把要访问的节点先都存起来，等到该去的时候，再一层层取出来，就像用一根绳子把它们串起来，拉出来的时候，结果就乖乖地在眼前了。

想象一下，树上的苹果，一个一个摘下来，效率简直高得惊人，没那么多折腾。

非递归的方式往往能让代码变得更加清晰，特别是当你给别人分享你的代码时，大家都能看得明白，不会一脸懵逼。

这样的好处简直就像是给大家开了一扇窗，阳光照进来，温暖了整个房间。

哎，真的是好得不得了。

说到大家不妨试试把自己的递归代码转换成非递归，可能会觉得自己像获得了一种新技能。

学会这一招，编程之路就更加宽广了，就像是打开了一扇新天地，眼前的风景愈加美丽。

不论是递归还是非递归，各有千秋，关键是看你自己怎么用。

编程的乐趣在于探索，敢于尝试，保持好奇心，那才是最重要的！好啦，今天的分享就到这里，祝大家编程愉快，玩得开心！。

迭代与递归和还原的关系

迭代与递归和还原的关系
迭代、递归和还原在计算机科学和数学中都有其特定的应用和关系，以下是它们之间的一些关系：
1. 递归与迭代：
递归是一种编程技巧，程序调用自身以解决问题。

递归将问题分解为更小的子问题，并逐个解决这些子问题，直到达到基本情况。

迭代则是通过重复执行一系列操作来解决问题，这些操作会根据某些条件进行修改，直到满足某个结束条件。

在理论上，递归和迭代的时间复杂度可能是相同的，但在实际应用中，由于函数调用和函数调用堆栈的开销，递归的效率通常较低。

理论上，递归和迭代可以相互转换。

例如，n的阶乘问题可以通过递归或迭代方法解决。

2. 迭代与还原：
还原通常指的是将一个复杂的问题或系统简化为一个或多个更简单的问题或子系统。

当使用迭代方法解决问题时，通常会将问题分解为一系列的步骤或操作，每一步都试图解决一部分问题，直到达到最终解决方案。

这种分步骤、分阶段解决问题的过程可以看作是一种还原的过程。

迭代方法通过将问题分解为更小的部分来解决问题，从而将一个复杂的问题还原为其基本的组成部分。

综上所述，递归、迭代和还原在解决问题的方法上有所不同，但它们在某些情况下可以相互关联或转换。

还原的概念可以看作是迭代方法的一个方面，因为迭代方法通过逐步解决较小的问题来还原问题的解决方案。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例：计算学生年龄第一个学生10岁第二个学生比第一个大两岁依次类推计算第n个学生的年龄？
#include<stdio.h> int age(int n) { int c; if(n==1) c=10; else c=age(n-1)+2; return c; } int main() { int n=5 ; printf("%d\n",age(n)); } #include<stdio.h> int age(int n) { int i=0; int s=10; for(i=0;i<=n;i++) { s=s+2; } return s; } void main() { int n=5; printf("%d\n",age(n)); }c来自p1cpp2返回
栈与递归的关系
函数递归是利用系统中栈进行操作的，通过对栈帧的一系列操作，从而实现递归。这个过程是由系统来完成的。在阶乘中，我们通过对阶乘的参数入栈，然后通过栈帧的一系列操作，从而实现参数的出栈，进而完成阶乘这个动作。整个过程实际上就是一个栈的入栈和出栈问题。
注：栈帧也叫过程活动记录，是编译器用来实现过程/函数调用的一种数据结构。
} e=s->data[s->top]; s->top--; return e; } int main(void) { sqstack jiecheng; jiecheng.top=-1; int x; int tmp=1,Sum=1; scanf("%d",&x); while(x) { push(&jiecheng,x--); } while(jiecheng.top!=-1) { tmp=pop(&jiecheng); Sum=Sum*tmp; } printf("sum is %d\n",Sum); return 0; cpp3 }
返回
Thank you
• 商务总结/毕业论文通用模板
递归函数与非递归函数的相互转化递归函数与栈的关系
一：递归与非递归二：递归与栈
递归与非递归
递归的代码量比非递归的代码量少，因为非递归需要额外的变量记录当前所处的位置信息，以及额外的控制语句。而递归所使用的方式是函数调用，这是非常自然的栈结构，不需要记录位置信息，不需要添加控制语句，这些工作都由函数调用的特性解决了。递归的执行效率比非递归的执行效率低，因为递归的实质是函数调用，而函数调用必然要进行线程栈空间的分配，记录每一次函数调用前的状态等工作，开销是比较大的。而非递归则不需要进行这些工作。
#include<stdio.h> #include<stdlib.h> #define maxsize 10 typedef struct { int top; int data[maxsize]; }sqstack; void push(sqstack *s,int e) { if(s->top==maxsize-1) { printf("stack is full"); exit(0); } s->top++; s->data[s->top]=e; } int pop(sqstack *s) { int e; if(s->top==-1) { printf("stack is empty"); exit(0);