c语言入门教程：函数递归

《c语言入门教程：函数递归》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C语言入门教程：函数递归C语言入门教程：函数递归.txt永远像孩子一样好奇，像年轻人一样改变，像中年人一样耐心，像老年人一样睿智。我的腰闪了，惹祸的不是青春，而是压力。。。。。。当女人不再痴缠，不再耍赖，不再喜怒无常，也就不再爱了。一、栈在说函数递归的时候，顺便说一下栈的概念。栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每

2、个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其

3、他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。二、递归递归，是函数实现的一个很重要的环节，很多程

4、序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能

5、正常工作。程序遍历执行这些函数的过程就被称为递归下降。程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。例如这样的程序就是递归：voida(int);main(){intnum=5;a(num);}voida(intnum){if(num==0)return;printf(%d,num);a(--num);}在函数a()里面又调用了自己，也就是自己调用本身，这样就是递归。那么有些人可能要想，这不是死循环吗？所以在递归函数中，一定要有return语句，没有return语句的递归

6、函数是死循环。我们分析上面的例子，先调用a(5)，然后输出5，再在函数中调用本身a(4)，接着回到函数起点，输出4，……，一直到调用a(0)，这时发现已经满足if条件，不在调用而是返回了，所以这个递归一共进行了5次。如果没有这个return，肯定是死循环的。虽然递归不难理解，但是很多在在使用递归函数的时候，问题多多。这里面一般有两个原因：一是如何往下递归，也就是不知道怎么取一个变量递归下去；二是不知道怎么终止递归，经常弄个死循环出来。下面看几个例子：1.求1+2+……+100的和先分析一下。第一递归变量的问题，从题目上看应该取1,2,……,100这些变量的值作为递归的条件；第二就是如

7、何终止的问题，从题目上看应该是当数为100的时候就不能往下加了。那么我们试着写一下程序。intadd(int);main(){intnum=1,sn;sn=add(num);printf(%d,sn);getch();}intadd(intnum){staticintsn;sn+=num;if(num==100)returnsn;add(++num);}分析一下程序：前调用add(1)，然后在子函数中把这个1加到sn上面。接着调用add(2)，再把sn