2024年10月递归调用栈的变化（递归、调用栈及尾递归）

　　⑴递归调用栈的变化（递归、调用栈及尾递归

　　⑵递归、调用栈及尾递归

　　⑶无论是否递归调用，当在一个函数(外层函数)的运行期间调用另一个函数（被调用函数，即内层函数时，在运行被调用函数之前，系统需要先完成个操作，即：

　　⑷从被调函数返回调用函数（外层函数之前，系统还要完成个操作，即：

　　⑸当有多个函数构成嵌套调用时，按照“后调用先返回“的原则，上述函数之间的信息传递和控制转移必须通过“栈“来实现，每当调用一个函数时，就在栈顶为它分配一个存储区，每当退出一个函数时，就释放它的存储区，当前正在运行的函数的数据区必在栈顶。递归函数的运行过程类似于多个函数的嵌套调用，只是调用和被调用函数是同一个函数。

　　⑹函数调用时，需要在栈中分配新的帧，将返回地址，调用参数和局部变量入栈。所以递归调用越深，占用的栈空间越多。

　　⑺为了解决递归的开销大问题，使用尾递归优化，具体分两步：

　　⑻使用尾递归的好处：因为进入下一层函数不再需要参考外层函数的信息，因此没必要保存外层函数的栈信息，递归需要用的stack只有目前这层被调用函数的，因此避免了栈溢出风险。一些语言提供了尾递归优化特性，当识别出使用了尾递归时，会相应地只保留当前层函数的stack，节省内存，不会发生stackOverflowException调用栈溢出。

　　⑼注意：JVM缺乏尾调用指令,java编译器对尾递归的优化未实现，所以在java中尽量避免过深的递归调用，如果需要使用递归，建议优化成迭代式。*

　　⑽尾递归就是操作的最后一步是调用自身的递归。注意，尾递归的判断标准是函数运行最后一步是否调用自身，而不是是否在函数的最后一行调用自身。这个不是尾递归：

　　⑾参考:.什么是尾递归.尾调用优化.栈是如何实现递归的:递归与栈一些不得不说的事.stack的三种含义

　　⑿递归调用太深，可能导致栈溢出

　　⒀栈溢出原因：因为每调用一个方法就会在栈上创建一个栈帧，方法调用结束后就会弹出该栈帧，而栈的大小不是无限的，所以递归调用次数过多的话就会导致栈溢出。而递归调用的特点是每递归一次，就要创建一个新的栈帧，而且还要保留之前的环境（栈帧，直到遇到结束条件。所以递归调用一定要明确好结束条件，不要出现死循环，而且要避免栈太深。解决方法：当遇到递归时，可能出现栈空间不足，出现栈溢出，再申请资源扩大栈空间，如果空间还是不足会出现内存溢出oom。合理的设置栈空间大小；写递归方法注意判断层次；能用递归的地方大多数能改写成非递归方式。

　　⒁递归函数到底是怎么进行调用的，栈怎么变化快速排序算法的递归过程是怎么样的

　　⒂快速排序中，首先要进行一次划分以确定轴值（即序列中在它右边都大于它，左边的都小于它的位置，快速排序中其实就是不停的对序列划分.比如：序列进行一次划分（即用一个函数实现后【】【】此时为轴值，然后对括号中的俩子序列分别进行快速排序！（既递归，调用自身函数。

　　⒃C语言递归进栈后何时出栈请大神详细点回答

　　⒄当最后一次递归调用结束的时候，开始依次出栈，出栈从最后那次调用开始，直到第一次调用结束。

　　⒅递归调用是一种特殊的嵌套调用，是某个函数调用自己或者是调用其他函数后再次调用自己的，只要函数之间互相调用能产生循环的则一定是递归调用，递归调用一种解决方案，一种是逻辑思想，将一个大工作分为逐渐减小的小工作。

　　⒆函数要直接或间接调用自身。

　　⒇要有递归终止条件检查，即递归终止的条件被满足后，则不再调用自身函数。

　　⒈如果不满足递归终止的条件，则调用涉及递归调用的表达式。在调用函数自身时，有关终止条件的参数要发生变化，而且需向递归终止的方向变化。

　　⒉递归调用之前的语句是从上到下的，函数调用之后的语句呢是从下到上的，因为后面的语句要等最下层或者最里面最后调用的那个函数执行之后不再调用了开始执行，然后返回上一层的时候再执行上一层函数调用后面的语句。并且特别注意的是，每次函数返回后直接就是函数调用后面的语句。

　　⒊递归其实就是利用了函数调用的一些特点，很巧妙的不断调用自己，把一个很大的问题分成了很多部分，让每一个函数解决一部分，并且上一层的结果编译器给我们保留了起来，返回的时候还能用。

　　⒋所以递归调用一定要是每深入一层都会把问题变得越来越小，而且最后能解决，不然就会无限制的调用自己，形成一个无限的循环，最后造成栈的溢出，最后程序崩溃。

　　⒌最近在看《算法图解》这本书，目前也在复习这些基础的算法知识，正好也可以在这里做一些总结，以加深自己的体会与理解。说到递归，对于一个接触过计算机科学领域的人来说再熟悉不过了，从字面的意思很容易理解，但是有很多人（比如我。。。看似能够理解递归的思路，实则一头雾水，以至于在解题的过程中会有很多的疑问和错误。下面就来分析一下递归的工作机制。计算机在内部使用调用栈的栈，我们来看看是如何使用调用栈的。下面是一个函数而另外两个函数：开始执行时，比如调用greet(“maggie“),计算机首先为该函数调用分配一块内存，将变量name设为maggie接下来，你打印hello,maggie!，再调用greet(“maggie“)。同样，计算机也为这个函数调用分配一块内存。计算机使用一个栈来表示这些内存块，其中第二个内存块位于第一个内存块上面。你打印howareyou,maggie?，然后从函数调用返回。此时，栈顶的内存块被弹出。现在，栈顶的内存块是函数greet的，这意味着你返回到了函数greet。当你调用函数greet时，函数greet只执行了一部分。这是本节的一个重要概念：调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。执行完函数greet后，你回到函数greet，并从离开的地方开始接着往下执行：首先打印gettingreadytosaybye…，再调用函数bye。在栈顶添加了函数bye的内存块。然后，你打印okbye!，并从这个函数返回

　　⒍递归首先是同一个函数的自身反复调用，每个函数的执行都需要一定的栈空间，那么如果递归层次太深的话就需要大量的空间，所以耗费资源。正常的函数调用会在调用结束后释放栈空间，但是递归调用只有在递归到最后一个层次的时候才开始逐步释放栈空间。你说的先进先出是指一种数据结构，函数运行使用的栈就是这种数据结构。

　　⒎递归算法和栈有什么关系栈又是怎样运用的

　　⒏递归算法和栈都有后进先出这个性质，基本上能用递归完成的算法都可以用栈完成，都是运用后进先出这个性质的用栈之前首先你要想明白你需要使用“后进先出”干什么，然后才可编写算法，使用中往往是先把数据都压入栈中，然后使用使取出便可，像表达式求解就是典型的运用栈的例子，可以去看看，会对栈的理解印象深刻些#include《stdio.h》#defineorigial#defineaddtypedefstruct{int*base;int*top;intstack;}opno;typedefstruct{char*base;char*top;intstack;}optr;voidinitstacka(opno*a){a-》base=(int*)malloc(sizeof(int)*origial);a-》top=a-》base;a-》stack=origial;}voidinitstackb(optr*b){b-》base=(char*)malloc(sizeof(char)*origial);b-》top=b-》base;b-》stack=origial;*b-》top++=’#’;}voidpusha(opno*a,intb){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;}voidpushb(optr*b,charc){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;}intdetermine(charc){if(c》=’’&&c《=’’)return();elsereturn();}chargettopb(optr*b){chara;a=*(b-》top-);return(a);}charshuzu(inti,intj){chara={{’》’,’》’,’《’,’《’,’《’,’》’,’》’},{’》’,’》’,’《’,’《’,’《’,’》’,’》’},{’》’,’》’,’》’,’》’,’《’,’》’,’》’},{’》’,’》’,’》’,’》’,’《’,’》’,’》’},{’《’,’《’,’《’,’《’,’《’,’=’,’’},{’》’,’》’,’》’,’》’,’’,’》’,’》’},{’《’,’《’,’《’,’《’,’《’,’’,’=’}};return(a);}charprecede(charb,chara){inti,j;chars;switch(b){case’+’:i=;break;case’-’:i=;break;case’*’:i=;break;case’/’:i=;break;case’(’:i=;break;case’)’:i=;break;case’#’:i=;break;}switch(a){case’+’:j=;break;case’-’:j=;break;case’*’:j=;break;case’/’:j=;break;case’(’:j=;break;case’)’:j=;break;case’#’:j=;break;}s=shuzu(i,j);return(s);}voidpopb(optr*a,char*b){*b=*--a-》top;}voidpopa(opno*a,int*b){*b=*--a-》top;}intcount(inta,intb,charc){intsum=;switch(c){case’+’:sum=a+b;break;case’-’:sum=a-b;break;case’*’:sum=a*b;break;case’/’:sum=a/b;break;}return(sum);}intempty(optr*a){if(a-》top==a-》base)return();elsereturn();}voidmain(){opno*a;optr*b;charc;chard;inti=,j=,k,sum=,p,o,r,w;inty;a=(opno*)malloc(sizeof(opno));b=(optr*)malloc(sizeof(optr));initstacka(a);initstackb(b);printf(“请输入表达式！

　　⒐“);scanf(“%s“,d);while(d!=’’)if(determine(d)){sum=;y-’’;while(determine(d)){i=i+;y-’’;}for(k=;k《=j;k++)sum=sum*+y;if(sum!=)pusha(a,sum);elsepusha(a,y);j=;for(k=;k《;k++)y=;i=i+;}else{switch(precede(gettopb(b),d)){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++;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);}这就是运用栈写得表达式求值

　　⒑递归函数到底是怎么进行调用的，栈怎么变化快速排序算法的递归过程是怎么样的

　　⒒快速排序中，首先要进行一次划分以确定轴值（即序列中在它右边都大于它，左边的都小于它的位置，快速排序中其实就是不停的对序列划分.比如：序列进行一次划分（即用一个函数实现后此时为轴值，然后对括号中的俩子序列分别进行快速排序！（既递归，调用自身函数。

　　⒓递归可以用栈实现吗？栈是如何实现递归的在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，毎个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。比如刚才的例子，总有一次递归会使得i《的，这样就可以执行returni的语句而不用继续递归了。对比了两种实现斐波那契的代码。迭代和递归的区别是：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。那么我们讲了这么多递归的内容，和栈有什么关系呢？这得从计算机系统的内部说起。前面我们已经看到递归是如何执行它的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。递归调用其实就是栈，栈有先进后出的特点，递归调用的实质也就是循环调用，我写一个简单的例子吧：