递归与栈

递归和栈有趣的对联上联：客上天然居居然天上客你能写下联吗？数列倒序问题有趣的对联客上天然居居然天上客人过大钟寺寺钟大过人压入过程居寺栈顶然钟天大上过客人栈底[问题描述]给定一个由N(1=N=26)个字符组成的序列，将这个序列按照倒序输出。不允许使用数组。[输入格式]第一行有一个数N，代表序列中字符的个数；第二行有N个字符，相邻两个字符间无空格符分隔；字符为英文小写字母或阿拉伯数字。[输出格式]输出一行，有N个字符的序列(是原序列按照逆序排列的结果)，相邻两个字符间无空格符分隔。[样例输入]8abcdefgh[样例输出]hgfedcba如果能用数组程序如下：#includeiostreamusingnamespacestd;intmain(){intn=0;cinn;//输入字符个数chars[26];//定义字符数组for(inti=0;in;i++)cins[i];//正序输入for(i=n-1;i=0;i--)couts[i];//逆序输出return0;}//theend不使用数组#includeiostreamusingnamespacestd;voidreserve(int);//声明有子函数intmain(){intn=0;//定义整数变量n初始化为0cinn;//健盘输入n的值reserve(n);//调用子函数，实参为n的值return0;//调用后的返回地址pn}voidreserve(intn){//定义子函数if(n==0)return;//递归的返回点chars;//定义字符变量scins;//键盘输入字符赋给sreserve(n-1);//递归调用couts;//输出s中的一个字符return;}//endoffile调用后的返回地址pn-1//函数功能为输入n个字符并逆序输出reserve(n)n==0n!=0return0返回点pn-1chars;couts;cins;return;reserve(n-1)为什么可以通过递归绕开线性存储结构，实现倒序的目的呢？我们研究“栈”。栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾称为栈顶(top)，相应地，表头称为栈底(bottom)。不含元素的空表称为空栈。假设栈S=(a1,a2,...,an),则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,...,an的次序进栈，退栈的第一个元素应为栈顶元素。因此，栈又称为后进先出(LastInFirstOut)的线性表(简称LIFO结构)，它的这个特点如下图所示。递归和栈栈想象子弹夹，先压进去的子弹最后打出来栈顶anan-1...栈底a1栈的两个基本操作：push:将一个元素推入栈顶pop:将栈顶（top）的元素弹出栈，并获得其访问权。注意：栈也是线性存储结构！忽略限制条件，问题可以通过栈结构来解决:(1)输入n;(2)输入一个数a，把a推入栈顶，n--;(3)若n0，则回到(2);(4)弹出栈顶元素并将其输出;(5)若栈非空，则回到(4);(6)结束程序.事实上，当做递归调用时，程序运行过程类似这样：(1)将函数调用完成后应该返回的位置p（作为一个指针）保存在栈顶；(2)调用函数；(3)函数调用完成后，弹出栈顶元素p，返回p所指向的位置继续运行程序。reserve(3)as返回点p2couts;return;reserve(2)输出abs返回点p1couts;return;reserve(1)输出bcs返回点p0couts;return;reserve(0)输出cp0p1输入顺序是abcp2输出顺序是cbap3#includeiostreamusingnamespacestd;voidreserve(int);//声明有子函数chars;intmain(){intn=3;//定义整数变量n初始化为0cinn;//键盘输入n的值reserve(n);//调用子函数，实参为n的值return0;//调用后的返回地址pn}voidreserve(intn){//定义子函数if(n==0)return;//递归的返回点chars;//定义字符变量scins;//键盘输入字符赋给scouts变量的地址是(void*)&s；s中的字符为sendl;reserve(n-1);//递归调用//调用后的返回地址p(n-1)couts变量的地址是(void*)&s；s中的字符为sendl;//输出s的地址和其中的一个字符return;}//endoffilevoidreserve(intn){//定义子函数if(n==0)return;//递归的返回点chars;//定义字符变量scins;//键盘输入字符赋给scouts变量的地址是(void*)&s；s中的字符为sendl;reserve(n-1);//递归调用//调用后的返回地址p(n-1)couts变量的地址是(void*)&s；s中的字符为sendl;//输出s的地址和其中的一个字符return;}//endoffilea屏幕显示s变量的地址是0012FF20；s中的字符为abs变量的地址是0012FEC4；s中的字符为bcs变量的地址是0012FE68；s中的字符为cs变量的地址是0012FE68；s中的字符为cs变量的地址是0012FEC4；s中的字符为bs变量的地址是0012FF20；s中的字符为a在系统的mainmemory中预留有一块叫作“栈”的区域做上面这项工作。当我们在做递归调用时，实际上是利用了系统中的“栈”帮我们完成了这项“艰巨”的任务。但是系统允许递归调用多少次呢？换句话说，栈能有多大呢？编个程序来测一测：#includeiostreamusingnamespacestd;voidtryIt(int);intmain(){tryIt(0);//用实参0调用tryIt函数return0;}voidtryIt(intn){//形参n的初始值为0coutnendl;//输出形参n的值tryIt(n+1);//用n+1的值调用tryIt函数return;}//EOF运行11741次递归结束条件非常重要，一定要保证函数在有限次调用后能够返回！递归是很有用的思考：将s定义为全局变量，会怎样？#includeiostreamusingnamespacestd;加上voidreserve(int);//声明有子函数chars;//定义字符变量sintmain(){intn=0;//定义整数变量n初始化为0cinn;//健盘输入n的值reserve(n);//调用子函数，实参为n的值return0;//调用后的返回地址pn}voidreserve(intn){//定义子函数去掉if(n==0)return;//递归的返回点//chars;//定义字符变量scins;//键盘输入字符赋给sreserve(n-1);//递归调用//调用后的返回地址pn-1couts;//输出s中的一个字符return;}//endoffile输出注意s是全局变量as变量的地址是0047B738;s中的字符为abs变量的地址是0047B738;s中的字符为bcs变量的地址是0047B738;s中的字符为cs变量的地址是0047B738;s中的字符为cs变量的地址是0047B738;s中的字符为cs变量的地址是0047B738;s中的字符为c结束