Ⅰ 递归调用底层堆栈原理是怎样的
请问楼主懂汇编吗？底层解释离不开汇编
目前C语言的函数实现：
当需要调用一个函数的时候，代码是需要从这里跳到其他地方（函数体）去执行的
这看上去似乎毫无疑问，但是当函数体执行完毕的时候，怎么回到原来的地方去执行呢？
需要知道回到哪里继续执行，就需要在进入函数的时候先把要返回的地址保存起来
这个返回地址就是保存在栈（注意是栈，堆跟栈是有区别的）中的！
下面举个例子
void f() f:
{
}
int main() 对应的部分汇编代码可能是：
{
f(); call f
}
现在我们把汇编代码对应的地址写上去(假定代码从内存0开始存放，每条指令长度都默认为1)
0 ; 函数f的首地址
1
2;ret
3 ;main的地址
4 ;call 0
5 ;ret
call 0 这个过程其实做了两件事情：
push 5 ;call指令下一条指令的地址
jmp 0;跳到f()处执行函数体
ret 过程也做类似的事情
从栈顶弹出一个字（32位下为双字）到(e)ip 然后去执行
有的时候，函数可能需要参数，这个时候参数也是被保存到栈中带到函数体中去的
再解释下去很复杂的，想知道 自己私m我吧
Ⅱ 递归文件夹堆栈溢出怎么解决
解决不了的。
不用递归结构，才行。
递归，是一种华而不实的技巧。
编程时，难以估量堆栈的大小。
只有在实用时，才知道递归的次数。
所以，设计堆栈时，大了浪费，小了溢出。
因此，递归，不过是一种华而不实的技巧，而已。
Ⅲ Java JVM 中怎么控制方法的递归调用。是在heap中的方法区，“重复”代码段吗
前面是我自己理解的后面是复制的
java有自动垃圾回收机制
当垃圾收集器判断已经没有任何引用指向对象的时候，会调用对象的finalize方法来释放对象占据的内存空间~
java中垃圾回收以前听老师讲好像是内存满了他才去做一次整体垃圾回收,在回收垃圾的同时会调用finalize方法.你在构造一个类时可以构造一个类时覆盖他的finalize方法以便于该类在被垃圾回收时执行一些代码,比如释放资源.
1.JVM的gc概述
gc即垃圾收集机制是指jvm用于释放那些不再使用的对象所占用的内存。java语言并不要求jvm有gc，也没有规定gc如何工作。不过常用的jvm都有gc，而且大多数gc都使用类似的算法管理内存和执行收集操作。
在充分理解了垃圾收集算法和执行过程后，才能有效的优化它的性能。有些垃圾收集专用于特殊的应用程序。比如，实时应用程序主要是为了避免垃圾收集中断，而大多数OLTP应用程序则注重整体效率。理解了应用程序的工作负荷和jvm支持的垃圾收集算法，便可以进行优化配置垃圾收集器。
垃圾收集的目的在于清除不再使用的对象。gc通过确定对象是否被活动对象引用来确定是否收集该对象。gc首先要判断该对象是否是时候可以收集。两种常用的方法是引用计数和对象引用遍历。
1.1.引用计数
引用计数存储对特定对象的所有引用数，也就是说，当应用程序创建引用以及引用超出范围时，jvm必须适当增减引用数。当某对象的引用数为0时，便可以进行垃圾收集。
1.2.对象引用遍历
早期的jvm使用引用计数，现在大多数jvm采用对象引用遍历。对象引用遍历从一组对象开始，沿着整个对象图上的每条链接，递归确定可到达（reachable）的对象。如果某对象不能从这些根对象的一个（至少一个）到达，则将它作为垃圾收集。在对象遍历阶段，gc必须记住哪些对象可以到达，以便删除不可到达的对象，这称为标记（marking）对象。
下一步，gc要删除不可到达的对象。删除时，有些gc只是简单的扫描堆栈，删除未标记的未标记的对象，并释放它们的内存以生成新的对象，这叫做清除（sweeping）。这种方法的问题在于内存会分成好多小段，而它们不足以用于新的对象，但是组合起来却很大。因此，许多gc可以重新组织内存中的对象，并进行压缩（compact），形成可利用的空间。
为此，gc需要停止其他的活动活动。这种方法意味着所有与应用程序相关的工作停止，只有gc运行。结果，在响应期间增减了许多混杂请求。另外，更复杂的 gc不断增加或同时运行以减少或者清除应用程序的中断。有的gc使用单线程完成这项工作，有的则采用多线程以增加效率。
2.几种垃圾回收机制
2.1.标记－清除收集器
这种收集器首先遍历对象图并标记可到达的对象，然后扫描堆栈以寻找未标记对象并释放它们的内存。这种收集器一般使用单线程工作并停止其他操作。
2.2.标记－压缩收集器
有时也叫标记－清除－压缩收集器，与标记－清除收集器有相同的标记阶段。在第二阶段，则把标记对象复制到堆栈的新域中以便压缩堆栈。这种收集器也停止其他操作。
2.3.复制收集器
这种收集器将堆栈分为两个域，常称为半空间。每次仅使用一半的空间，jvm生成的新对象则放在另一半空间中。gc运行时，它把可到达对象复制到另一半空间，从而压缩了堆栈。这种方法适用于短生存期的对象，持续复制长生存期的对象则导致效率降低。
2.4.增量收集器
增量收集器把堆栈分为多个域，每次仅从一个域收集垃圾。这会造成较小的应用程序中断。
2.5.分代收集器
这种收集器把堆栈分为两个或多个域，用以存放不同寿命的对象。jvm生成的新对象一般放在其中的某个域中。过一段时间，继续存在的对象将获得使用期并转入更长寿命的域中。分代收集器对不同的域使用不同的算法以优化性能。
2.6.并发收集器
并发收集器与应用程序同时运行。这些收集器在某点上（比如压缩时）一般都不得不停止其他操作以完成特定的任务，但是因为其他应用程序可进行其他的后台操作，所以中断其他处理的实际时间大大降低。
2.7.并行收集器
并行收集器使用某种传统的算法并使用多线程并行的执行它们的工作。在多cpu机器上使用多线程技术可以显着的提高java应用程序的可扩展性。
3.Sun HotSpot
1.4.1 JVM堆大小的调整
Sun HotSpot 1.4.1使用分代收集器，它把堆分为三个主要的域：新域、旧域以及永久域。Jvm生成的所有新对象放在新域中。一旦对象经历了一定数量的垃圾收集循环后，便获得使用期并进入旧域。在永久域中jvm则存储class和method对象。就配置而言，永久域是一个独立域并且不认为是堆的一部分。
下面介绍如何控制这些域的大小。可使用-Xms和-Xmx 控制整个堆的原始大小或最大值。
下面的命令是把初始大小设置为128M：
java –Xms128m
–Xmx256m为控制新域的大小，可使用-XX:NewRatio设置新域在堆中所占的比例。
下面的命令把整个堆设置成128m，新域比率设置成3，即新域与旧域比例为1：3，新域为堆的1/4或32M：
java –Xms128m –Xmx128m
–XX:NewRatio =3可使用-XX:NewSize和-XX:MaxNewsize设置新域的初始值和最大值。
下面的命令把新域的初始值和最大值设置成64m:
java –Xms256m –Xmx256m –Xmn64m
永久域默认大小为4m。运行程序时，jvm会调整永久域的大小以满足需要。每次调整时，jvm会对堆进行一次完全的垃圾收集。
使用-XX:MaxPerSize标志来增加永久域搭大小。在WebLogic Server应用程序加载较多类时，经常需要增加永久域的最大值。当jvm加载类时，永久域中的对象急剧增加，从而使jvm不断调整永久域大小。为了避免调整，可使用-XX:PerSize标志设置初始值。
下面把永久域初始值设置成32m，最大值设置成64m。
java -Xms512m -Xmx512m -Xmn128m -XX:PermSize=32m -XX:MaxPermSize=64m
默认状态下，HotSpot在新域中使用复制收集器。该域一般分为三个部分。第一部分为Eden，用于生成新的对象。另两部分称为救助空间，当Eden 充满时，收集器停止应用程序，把所有可到达对象复制到当前的from救助空间，一旦当前的from救助空间充满，收集器则把可到达对象复制到当前的to救助空间。From和to救助空间互换角色。维持活动的对象将在救助空间不断复制，直到它们获得使用期并转入旧域。使用-XX:SurvivorRatio 可控制新域子空间的大小。
同NewRation一样，SurvivorRation规定某救助域与Eden空间的比值。比如，以下命令把新域设置成64m，Eden占32m，每个救助域各占16m：
java -Xms256m -Xmx256m -Xmn64m -XX:SurvivorRation =2
如前所述，默认状态下HotSpot对新域使用复制收集器，对旧域使用标记－清除－压缩收集器。在新域中使用复制收集器有很多意义，因为应用程序生成的大部分对象是短寿命的。理想状态下，所有过渡对象在移出Eden空间时将被收集。如果能够这样的话，并且移出Eden空间的对象是长寿命的，那么理论上可以立即把它们移进旧域，避免在救助空间反复复制。但是，应用程序不能适合这种理想状态，因为它们有一小部分中长寿命的对象。最好是保持这些中长寿命的对象并放在新域中，因为复制小部分的对象总比压缩旧域廉价。为控制新域中对象的复制，可用-XX:TargetSurvivorRatio控制救助空间的比例（该值是设置救助空间的使用比例。如救助空间位1M，该值50表示可用500K）。该值是一个百分比，默认值是50。当较大的堆栈使用较低的 sruvivorratio时，应增加该值到80至90，以更好利用救助空间。用-XX:maxtenuring threshold可控制上限。
为放置所有的复制全部发生以及希望对象从eden扩展到旧域，可以把MaxTenuring Threshold设置成0。设置完成后，实际上就不再使用救助空间了，因此应把SurvivorRatio设成最大值以最大化Eden空间，设置如下：
java … -XX:MaxTenuringThreshold=0 –XX:SurvivorRatio＝50000 …
4.BEA JRockit JVM的使用
Bea WebLogic 8.1使用的新的JVM用于Intel平台。在Bea安装完毕的目录下可以看到有一个类似于jrockit81sp1_141_03的文件夹。这就是 Bea新JVM所在目录。不同于HotSpot把Java字节码编译成本地码，它预先编译成类。JRockit还提供了更细致的功能用以观察JVM的运行状态，主要是独立的GUI控制台（只能适用于使用Jrockit才能使用jrockit81sp1_141_03自带的console监控一些cpu及 memory参数）或者WebLogic Server控制台。
Bea JRockit JVM支持4种垃圾收集器：
4.1.1.分代复制收集器
它与默认的分代收集器工作策略类似。对象在新域中分配，即JRockit文档中的nursery。这种收集器最适合单cpu机上小型堆操作。
4.1.2.单空间并发收集器
该收集器使用完整堆，并与背景线程共同工作。尽管这种收集器可以消除中断，但是收集器需花费较长的时间寻找死对象，而且处理应用程序时收集器经常运行。如果处理器不能应付应用程序产生的垃圾，它会中断应用程序并关闭收集。
分代并发收集器这种收集器在护理域使用排它复制收集器，在旧域中则使用并发收集器。由于它比单空间共同发生收集器中断频繁，因此它需要较少的内存，应用程序的运行效率也较高，注意，过小的护理域可以导致大量的临时对象被扩展到旧域中。这会造成收集器超负荷运作，甚至采用排它性工作方式完成收集。
4.1.3.并行收集器
该收集器也停止其他进程的工作，但使用多线程以加速收集进程。尽管它比其他的收集器易于引起长时间的中断，但一般能更好的利用内存，程序效率也较高。
默认状态下，JRockit使用分代并发收集器。要改变收集器，可使用-Xgc:，对应四个收集器分别为 gen，singlecon，gencon以及parallel。可使用-Xms和-Xmx设置堆的初始大小和最大值。要设置护理域，则使用- Xns:java –jrockit –Xms512m –Xmx512m –Xgc:gencon –Xns128m…尽管JRockit支持-verbose:gc开关，但它输出的信息会因收集器的不同而异。JRockit还支持memory、 load和codegen的输出。
注意 ：如果 使用JRockit JVM的话还可以使用WLS自带的console（C:\bea\jrockit81sp1_141_03\bin下）来监控一些数据，如cpu， memery等。要想能构监控必须在启动服务时startWeblogic.cmd中加入－Xmanagement参数。
5.如何从JVM中获取信息来进行调整
-verbose.gc开关可显示gc的操作内容。打开它，可以显示最忙和最空闲收集行为发生的时间、收集前后的内存大小、收集需要的时间等。打开- xx:+ printgcdetails开关，可以详细了解gc中的变化。打开-XX: + PrintGCTimeStamps开关，可以了解这些垃圾收集发生的时间，自jvm启动以后以秒计量。最后，通过-xx: + PrintHeapAtGC开关了解堆的更详细的信息。为了了解新域的情况，可以通过-XX:=PrintTenuringDistribution开关了解获得使用期的对象权。
6.Pdm系统JVM调整
6.1.服务器：前提内存1G 单CPU
可通过如下参数进行调整：－server 启用服务器模式（如果CPU多，服务器机建议使用此项）
－Xms,－Xmx一般设为同样大小。 800m
－Xmn 是将NewSize与MaxNewSize设为一致。320m
－XX:PerSize 64m
－XX:NewSize 320m 此值设大可调大新对象区，减少Full GC次数
－XX:MaxNewSize 320m
－XX:NewRato NewSize设了可不设。
－XX: SurvivorRatio
－XX:userParNewGC 可用来设置并行收集
－XX:ParallelGCThreads 可用来增加并行度
－XXUseParallelGC 设置后可以使用并行清除收集器
－XX：UseAdaptiveSizePolicy 与上面一个联合使用效果更好，利用它可以自动优化新域大小以及救助空间比值
6.2.客户机：通过在JNLP文件中设置参数来调整客户端JVM
JNLP中参数：initial-heap-size和max-heap-size
这可以在framework的RequestManager中生成JNLP文件时加入上述参数，但是这些值是要求根据客户机的硬件状态变化的（如客户机的内存大小等）。建议这两个参数值设为客户机可用内存的60％（有待测试）。为了在动态生成JNLP时以上两个参数值能够随客户机不同而不同，可靠虑获得客户机系统信息并将这些嵌到首页index.jsp中作为连接请求的参数。
在设置了上述参数后可以通过Visualgc 来观察垃圾回收的一些参数状态，再做相应的调整来改善性能。一般的标准是减少fullgc的次数，最好硬件支持使用并行垃圾回收（要求多CPU）。
Ⅳ java 递归和内存的堆栈
基本数据类型就是在栈里面开辟一块空间，把里面的值存进去。例如 : int i = 9; 就是开辟一块内存，那块内存的名字叫i，里面的值存放的9; 引用数据类型也是在栈开辟一块空间，当new 对象的时候就会在堆里面开辟一块空间，存储这个对象的所有信息，然后栈的那块空间里面的值就会变成一系列内存地址，可以指向堆里面的那块内存。 例如: Date date; 这个就是在栈里面开辟了块内存，名字叫date，然后它里面的值为null; date = new Date(); 然后这个就是在堆开辟了块内存，把所有信息都放进去了，然后栈内存的date里面的值就会变成指向堆内存的地址。 所以你调用date的时候就相当是在调用堆里面的数据.
Ⅳ 有没有办法在递归函数里面得到递归栈的内容
你自己查看调用堆栈就可以看堆栈里面的内容吧。另外，你在递归函数里面设断点，一步步的堆栈调用你都可以看到的。还可以看当时的汇编代码。
Ⅵ 下一个堆栈的地址保存在哪里
堆栈中， 存储的是相同类型的元素
所以每个元素大小相同
只需要知道栈顶指针就可以了
这个就是指向下一个元素的。
所以 下一个堆栈地址就是栈顶指针。
Ⅶ 怎样用递归的方法遍历栈
如何用栈实现递归与非递归的转换
分类： C/C++2010-07-12 14:4012人阅读评论(0)收藏举报
如何用栈实现递归与非递归的转换一.为什么要学习递归与非递归的转换的实现方法? 1)并不是每一门语言都支持递归的. 2)有助于理解递归的本质. 3)有助于理解栈,树等数据结构.二.递归与非递归转换的原理. 递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的. 学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了. 1)前序遍历 a)递归方式:
void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */
{
if (T) {
visit(T); /* 访问当前结点 */
preorder_recursive(T->;lchild); /* 访问左子树 */
preorder_recursive(T->;rchild); /* 访问右子树 */
}
}
复制代码
b)非递归方式
void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法 */
{
initstack(S);
push(S,T); /* 根指针进栈 */
while(!stackempty(S)) {
while(gettop(S,p)&&p) { /* 向左走到尽头 */
visit(p); /* 每向前走一步都访问当前结点 */
push(S,p->;lchild);
}
pop(S,p);
if(!stackempty(S)) { /* 向右走一步 */
pop(S,p);
push(S,p->;rchild);
}
}
}
复制代码
2)中序遍历 a)递归方式
void inorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */
{
if (T) {
inorder_recursive(T->;lchild); /* 访问左子树 */
visit(T); /* 访问当前结点 */
inorder_recursive(T->;rchild); /* 访问右子树 */
}
}
复制代码
b)非递归方式
void inorder_nonrecursive(Bitree T)
{
initstack(S); /* 初始化栈 */
push(S, T); /* 根指针入栈 */
while (!stackempty(S)) {
while (gettop(S, p) && p) /* 向左走到尽头 */
push(S, p->;lchild);
pop(S, p); /* 空指针退栈 */
if (!stackempty(S)) {
pop(S, p);
visit(p); /* 访问当前结点 */
push(S, p->;rchild); /* 向右走一步 */
}
}
}
复制代码
3)后序遍历 a)递归方式
void postorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法 */
{
if (T) {
postorder_recursive(T->;lchild); /* 访问左子树 */
postorder_recursive(T->;rchild); /* 访问右子树 */
visit(T); /* 访问当前结点 */
}
}
复制代码
b)非递归方式
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有mark域的结点指针类型 */
void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法 */
{
PMType a;
initstack(S); /* S的元素为PMType类型 */
push (S,{T,0}); /* 根结点入栈 */
while(!stackempty(S)) {
pop(S,a);
switch(a.mark)
{
case 0:
push(S,{a.ptr,1}); /* 修改mark域 */
if(a.ptr->;lchild)
push(S,{a.ptr->;lchild,0}); /* 访问左子树 */
break;
case 1:
push(S,{a.ptr,2}); /* 修改mark域 */
if(a.ptr->;rchild)
push(S,{a.ptr->;rchild,0}); /* 访问右子树 */
break;
case 2:
visit(a.ptr); /* 访问结点 */
}
}
}
复制代码
4)如何实现递归与非递归的转换 通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递 给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调 函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数. 所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存 就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现 同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上 面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三 种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以 得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次 处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明:
void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法 */
{
if (T) {
visit(T); /* 访问当前结点 */
preorder_recursive(T->;lchild); /* 访问左子树 */
preorder_recursive(T->;rchild); /* 访问右子树 */
}
}
复制代码
visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->;lchild)就是把当前 数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a) 确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结 构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用 树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的 "叶子结点". 三.三个例子 好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识 .即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明 白(事实上我也是花了两个星期的时间才弄得比较明白得). 1)例子一:
f(n) = n + 1; (n <2)
f[n/2] + f[n/4](n >;= 2);
这个例子相对简单一些,递归程序如下:
int f_recursive(int n)
{
int u1, u2, f;
if (n < 2)
f = n + 1;
else {
u1 = f_recursive((int)(n/2));
u2 = f_recursive((int)(n/4));
f = u1 * u2;
}
return f;
}
复制代码
下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点 ,我们看到当n < 2时f = n + 1,这就是返回的语句,有人问为什么不是f = u1 * u2,这也是一个 返回的语句呀?答案是:这条语句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之后 执行的,是这两条语句的父结点. 其次,什么是当前结点,由上面的分析,f = u1 * u2即是父结点 .然后,顺理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分别是左子树和右子 树了.最后,我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树.好了,树的情况分析 到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中,在上面给出的后序遍历的如果这个过程你没 非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域;另外,u1,u2和 每次调用递归函数时的n/2和n/4参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量 和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也 只有在向上返回时才用到,因此可以把这两个栈合为一个栈.如果对于上面的分析你没有明白,建 议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和 栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,最好把递归调用树和 栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里. ok,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来 的).
int f_nonrecursive(int n)
{
int stack[20], flag[20], cp;
/* 初始化栈和栈顶指针 */
cp = 0;
stack[0] = n;
flag[0] = 0;
while (cp >;= 0) {
switch(flag[cp]) {
case 0: /* 访问的是根结点 */
if (stack[cp] >;= 2) { /* 左子树入栈 */
flag[cp] = 1; /* 修改标志域 */
cp++;
stack[cp] = (int)(stack[cp - 1] / 2);
flag[cp] = 0;
} else { /* 否则为叶子结点 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 1: /* 访问的是左子树 */
if (stack[cp] >;= 2) { /* 右子树入栈 */
flag[cp] = 2; /* 修改标志域 */
cp += 2;
stack[cp] = (int)(stack[cp - 2] / 4);
flag[cp] = 1;
} else { /* 否则为叶子结点 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 2: /* */
if (flag[cp - 1] == 2) { /* 当前是右子树吗? */
/*
* 如果是右子树, 那么对某一棵子树的后序遍历已经
* 结束,接下来就是对这棵子树的根结点的访问
*/
stack[cp - 2] = stack[cp] * stack[cp - 1];
flag[cp - 2] = 2;
cp = cp - 2;
} else
/* 否则退回到后序遍历的上一个结点 */
cp--;
break;
}
}
return stack[0];
}
复制代码
算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示 已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.b)每 遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据 访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向. 2)例子二 快速排序算法 递归算法如下:
void swap(int array[], int low, int high)
{
int temp;
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
int partition(int array[], int low, int high)
{
int p;
p = array[low];
while (low < high) {
while (low < high && array[high] >;= p)
high--;
swap(array,low,high);
while (low < high && array[low] <= p)
low++;
swap(array,low,high);
}
return low;
}
void qsort_recursive(int array[], int low, int high)
{
int p;
if(low < high) {
p = partition(array, low, high);
qsort_recursive(array, low, p - 1);
qsort_recursive(array, p + 1, high);
}
}
复制代码
需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分, 左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分.这 里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实 partition函数就是对当前结点的访问). 再次进行递归调用树和栈的分析: 递归调用树:a)对当前结点的访问是调用partition函数;b)左子树: qsort_recursive(array, low, p - 1);c)右子树:qsort_recursive(array, p + 1, high); d)叶子结点:当low < high时;e)可以看出这是一个先序调用的二叉树 栈:要保存的数据是两个表示范围的坐标.
void qsort_nonrecursive(int array[], int low, int high)
{
int m[50], n[50], cp, p;
/* 初始化栈和栈顶指针 */
cp = 0;
m[0] = low;
n[0] = high;
while (m[cp] < n[cp]) {
while (m[cp] < n[cp]) { /* 向左走到尽头 */
p = partition(array, m[cp], n[cp]); /* 对当前结点的访问 */
cp++;
m[cp] = m[cp - 1];
n[cp] = p - 1;
}
/* 向右走一步 */
m[cp + 1] = n[cp] + 2;
n[cp + 1] = n[cp - 1];
cp++;
}
}
复制代码
3)例子三 阿克曼函数:
akm(m, n) = n + 1; (m = 0时)
akm(m - 1, 1); (n = 0时)
akm(m - 1, akm(m, n - 1)); (m != 0且n != 0时)
复制代码
递归算法如下:
int akm_recursive(int m, int n)
{
int temp;
if (m == 0)
return (n + 1);
else if (n == 0)
return akm_recursive(m - 1, 1);
else {
temp = akm_recursive(m, n - 1);
return akm_recursive(m - 1, temp);
}
}
Ⅷ 递归算法和栈有什么关系栈又是怎样运用的
递归算法和栈都有后进先出这个性质，基本上能用递归完成的算法都可以用栈完成，都是运用后进先出这个性质的
用栈之前首先你要想明白你需要使用“后进先出”干什么，然后才可编写算法，使用中往往是先把数据都压入栈中，然后使用使取出便可，
像表达式求解就是典型的运用栈的例子，可以去看看，会对栈的理解印象深刻些
# include <stdio.h>
# define origial 100
# define add 10
typedef struct
{
int *base;
int *top;
int stack;
}opno;
typedef struct
{
char *base;
char *top;
int stack;
}optr;
void initstacka(opno *a)
{
a->base=(int *)malloc(sizeof(int)*origial);
a->top=a->base;
a->stack=origial;
}
void initstackb(optr *b)
{
b->base=(char *)malloc(sizeof(char)*origial);
b->top=b->base;
b->stack=origial;
*b->top++='#';
}
void pusha(opno *a,int b)
{
if(a->top-a->base>=a->stack)
{
a->base=(int *)realloc(a->base,sizeof(int)*(a->stack+add));
a->top=a->base+a->stack;
a->stack+=add;
}
*a->top++=b;
}
void pushb(optr *b,char c)
{
if(b->top-b->base>=b->stack)
{
b->base=(char *)realloc(b->base,sizeof(char)*(b->stack+add));
b->top=b->base+b->stack;
b->stack+=add;
}
*b->top++=c;
}
int determine(char c)
{
if(c>='0'&&c<='9')
return(1);
else
return(0);
}
char gettopb(optr *b)
{
char a;
a=*(b->top-1);
return(a);
}
char shuzu(int i,int j)
{
char a[7][7]={{'>','>','<','<','<','>','>'},{'>','>','<','<','<','>','>'},{'>','>','>','>','<','>','>'},{'>','>','>','>','<','>','>'},{'<','<','<','<','<','=','0'},{'>','>','>','>','0','>','>'},{'<','<','<','<','<','0','='}};
return(a[i][j]);
}
char precede(char b,char a)
{
int i,j;
char s;
switch(b)
{
case '+':i=0;
break;
case '-':i=1;
break;
case '*':i=2;
break;
case '/':i=3;
break;
case '(':i=4;
break;
case ')':i=5;
break;
case '#':i=6;
break;
}
switch(a)
{
case '+':j=0;
break;
case '-':j=1;
break;
case '*':j=2;
break;
case '/':j=3;
break;
case '(':j=4;
break;
case ')':j=5;
break;
case '#':j=6;
break;
}
s=shuzu(i,j);
return(s);
}
void popb(optr *a,char *b)
{
*b=*--a->top;
}
void popa(opno *a,int *b)
{
*b=*--a->top;
}
int count(int a,int b,char c)
{
int sum=0;
switch(c)
{
case '+':sum=a+b;
break;
case '-':sum=a-b;
break;
case '*':sum=a*b;
break;
case '/':sum=a/b;
break;
}
return(sum);
}
int empty(optr *a)
{
if(a->top==a->base)
return(1);
else
return(0);
}
void main()
{
opno *a;
optr *b;
char c;
char d[50];
int i=0,j=0,k,sum=0,p,o,r,w;
int y[3];
a=(opno *)malloc(sizeof(opno));
b=(optr *)malloc(sizeof(optr));
initstacka(a);
initstackb(b);
printf("请输入表达式！\n");
scanf("%s",d);
while(d[i]!='#'&&d[i]!='\0')
if(determine(d[i]))
{
sum=0;
y[j]=d[i]-'0';
while(determine(d[i+1]))
{
i=i+1;
y[++j]=d[i]-'0';
}
for(k=0;k<=j;k++)
sum=sum*10+y[k];
if(sum!=0)
pusha(a,sum);
else
pusha(a,y[0]);
j=0;
for(k=0;k<3;k++)
y[k]=0;
i=i+1;
}
else
{
switch(precede(gettopb(b),d[i]))
{
case '>':popb(b,&c);
popa(a,&p);
popa(a,&o);
r=count(o,p,c);
pusha(a,r);
break;
case '=':popb(b,&c);
i++;
break;
case '<':pushb(b,d[i]);
i++;
break;
}
}
popb(b,&c);
while(c!='#')
{
popa(a,&o);
popa(a,&p);
r=count(o,p,c);
pusha(a,r);
popb(b,&c);
}
popa(a,&w);
printf("%d",w);
}
这就是运用栈写得表达式求值
Ⅸ 在单片机PUSH指令如何使用的，是怎样把数据保存在堆栈区的。又是如何恢复的
PUSH A 错，如果是PUSH ACC就对了
PUSH B 对
PUSH PSW 对
PUSH R0 错
51单片机中，所有SFR寄存器可以用名称入栈，通用寄存器只能用直接寻址
Ⅹ 递归调用时,栈中保存的是函数的返回值吗
一般是，函数执行到那一步的地址、这一次函数执行时的参数变量，递归触底后、逐级返回时压入返回值到调用该次函数的函数地址参数变量堆栈上。说的可能不好理解，但是递归描述就是很麻烦，希望有高手给个简单明了的描述。