递归与栈讲解学习

递归和栈有趣的对联上联(shànglián)：客上天然居居然天上客你能写下联吗？第一页，共25页。数列倒序问题有趣的对联客上天然居居然(jūrán)天上客人过大钟寺寺钟大过人第二页，共25页。压入过程(guòchéng)居寺栈顶然钟天大上过客人栈底第三页，共25页。[问题描述]

给定一个由N(1<=N<=26)个字符组成的序列，将这个序列按照倒序输出。不允许使用数组。[输入格式]

第一行有一个数N，代表序列中字符的个数；

第二行有N个字符，相邻两个字符间无空格符分隔；

字符为英文小写字母或阿拉伯数字。[输出格式]

输出一行，有N个字符的序列(是原序列按照逆序排列(páiliè)的结果)，相邻两个字符间无空格符分隔。[样例输入]8abcdefgh[样例输出]hgfedcba第四页，共25页。如果能用数组程序如下(rúxià)：#include<iostream>usingnamespacestd;intmain(){intn=0;cin>>n;//输入字符个数chars[26];//定义字符数组for(inti=0;i<n;i++)cin>>s[i];//正序输入for(i=n-1;i>=0;i--)cout<<s[i];//逆序输出return0;}//theend第五页，共25页。不使用数组#include<iostream>usingnamespacestd;voidreserve(int);//声明有子函数intmain(){ intn=0;//定义整数变量n初始化为0 cin>>n;//健盘输入(shūrù)n的值 reserve(n);//调用子函数，实参为n的值 return0;//调用后的返回地址pn}第六页，共25页。voidreserve(intn){//定义子函数 if(n==0)return;//递归的返回点 chars;//定义字符变量s cin>>s;//键盘输入字符赋给s reserve(n-1);//递归调用 cout<<s;//输出s中的一个(yīɡè)字符 return;}//endoffile调用后的返回地址pn-1//函数功能为输入n个字符并逆序输出第七页，共25页。reserve(n)n==0n!=0return0返回(fǎnhuí)点pn-1chars;cout<<s;cin>>s;return;reserve(n-1)第八页，共25页。为什么可以通过递归绕开线性存储(cúnchǔ)结构，实现倒序的目的呢？我们研究“栈”。栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾称为栈顶(top)，相应地，表头称为栈底(bottom)。不含元素的空表称为空栈。假设栈S=(a1,a2,...,an),则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,...,an的次序进栈，退栈的第一个元素应为栈顶元素。因此，栈又称为后进先出(LastInFirstOut)的线性表(简称LIFO结构)，它的这个特点如下图所示。

第九页，共25页。递归和栈栈想象子弹(zǐdàn)夹，先压进去的子弹(zǐdàn)最后打出来栈顶anan-1...栈底a1第十页，共25页。栈的两个基本操作： push:将一个元素推入栈顶 pop:将栈顶（top）的元素弹出栈，并获得其访问权。 注意(zhùyì)：栈也是线性存储结构！第十一页，共25页。忽略限制条件，问题可以(kěyǐ)通过栈结构来解决: (1)输入n; (2)输入一个数a，把a推入栈顶，n--; (3)若n>0，则回到(2); (4)弹出栈顶元素并将其输出; (5)若栈非空，则回到(4); (6)结束程序.第十二页，共25页。事实上，当做递归调用时，程序运行过程(guòchéng)类似这样：

(1)将函数调用完成后应该返回的位置p（作为一个指针）保存在栈顶； (2)调用函数； (3)函数调用完成后，弹出栈顶元素p，返回p所指向的位置继续运行程序。第十三页，共25页。reserve(3)as返回点p2cout<<s;return;reserve(2)输出(shūchū)abs返回点p1cout<<s;return;reserve(1)输出(shūchū)bcs返回点p0cout<<s;return;reserve(0)输出(shūchū)cp0p1输入顺序是abcp2输出(shūchū)顺序是cbap3第十四页，共25页。#include<iostream>usingnamespacestd;voidreserve(int);//声明有子函数chars;intmain(){ intn=3;//定义整数变量n初始化为0 cin>>n;//键盘输入n的值 reserve(n);//调用子函数，实参为n的值 return0;//调用后的返回(fǎnhuí)地址pn}第十五页，共25页。voidreserve(intn){//定义子函数 if(n==0)return;//递归的返回(fǎnhuí)点 chars;//定义字符变量s cin>>s;//键盘输入字符赋给s cout<<"s变量的地址是"<<(void*)&s<<"；s中的字符为"<<s<<endl; reserve(n-1);//递归调用//调用后的返回(fǎnhuí)地址p(n-1)cout<<"s变量的地址是"<<(void*)&s<<"；s中的字符为"<<s<<endl;//输出s的地址和其中的一个字符 return;}//endoffile第十六页，共25页。voidreserve(intn){//定义子函数 if(n==0)return;//递归的返回(fǎnhuí)点 chars;//定义字符变量s cin>>s;//键盘输入字符赋给s cout<<"s变量的地址是"<<(void*)&s<<"；s中的字符为"<<s<<endl; reserve(n-1);//递归调用//调用后的返回(fǎnhuí)地址p(n-1)cout<<"s变量的地址是"<<(void*)&s<<"；s中的字符为"<<s<<endl;//输出s的地址和其中的一个字符 return;}//endoffile第十七页，共25页。a屏幕显示s变量的地址(dìzhǐ)是0012FF20；s中的字符为abs变量的地址(dìzhǐ)是0012FEC4；s中的字符为bcs变量的地址(dìzhǐ)是0012FE68；s中的字符为cs变量的地址(dìzhǐ)是0012FE68；s中的字符为cs变量的地址(dìzhǐ)是0012FEC4；s中的字符为bs变量的地址(dìzhǐ)是0012FF20；s中的字符为a第十八页，共25页。在系统的mainmemory中预留有一块叫作“栈”的区域做上面这项工作(gōngzuò)。当我们在做递归调用时，实际上是利用了系统中的“栈”帮我们完成了这项“艰巨”的任务。但是系统允许递归调用多少次呢？换句话说，栈能有多大呢？编个程序来测一测：第十九页，共25页。#include<iostream>usingnamespacestd;voidtryIt(int);intmain(){ tryIt(0);//用实参0调用(diàoyòng)tryIt函数 return0;}voidtryIt(intn){//形参n的初始值为0 cout<<n<<endl;//输出形参n的值 tryIt(n+1);//用n+1的值调用(diàoyòng)tryIt函数 return;}//EOF运行11741次第二十页，共25页。递归结束条件非常重要，一定(yīdìng)要保证函数在有限次调用后能够返回！递归是很有用的第二十一页，共25页。思考：将s定义为全局变量，会怎样？#include<iostream>usingnamespacestd;加上voidreserve(int);//声明(shēngmíng)有子函数chars;//定义字符变量sintmain(){ intn=0;//定义整数变量n初始化为0 cin>>n;//健盘输入n的值 reserve(n);//调用子函数，实参为n的值 return0