栈及栈的应用

1、内容提要1、栈的概念和特性；2、栈的存储结构；3、栈的几种运算（操作）实现;4、栈的应用举例；重点难点1、栈的概念和特性;2、栈的应用场合；3、栈的操作实现；内容讲授1. 栈的概念和特性栈（stack ）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗 看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。 而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。好果我们把冼 净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么，上例的特点是： 后进栈的先出栈。然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”都在最顶

2、上进行，或者说，元素的插入和删除是在表的一端进行而已。一般而言，栈是一个线性表，其所有的插入和删除均是限定在表的一端进行，允许插入和删除的一端称栈顶（Top），不允许插入和删除的一端称栈底 （Bottom）。若给定一个栈S=（ai, a2, a3,，an）,则称ai为栈底元素，an为栈顶元素，元素ai位于元素an之上。栈中元素按a1, a2,a3,，an的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an, an-1，,a1。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。因此 栈又称为后进先出（LIFO Last In First Out） 表。通常，对栈进行的运

3、算主要有以下几种：在使用栈之前，首先需要建立一个空栈，称建栈;往栈顶加入一个新元素，称进栈（压栈）；删除栈顶元素，称出栈(退栈、弹出)；查看当前的栈顶元素，称读栈；注意与的区别在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。2 栈的存储结构栈是一种线性表，在计算机中用向量作为栈的存储结构最为简单。因此，当用编程语 言写程序时，用一维数组来建栈十分方便。例如，设一维数组STACK1. .n表示一个栈，其中n为栈的容量，即可存放元素的最大个数。栈的第一个元素，或称栈底元素，是存放在STACK1处，第二个元素存放在STACK2处，第i个元素存放在 STACKi处。另外，由于栈顶元素经常变

4、动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0 ,当top=n时，表示栈满。如果一个栈已经为空，但用户还继续做出栈(读栈)操作，则会出现栈的“下溢”；如 果一个栈已经满了，用户还继续做进栈操作，则会出现栈的“上溢”。两种情况统称为栈的 溢出。3对栈的几种运算的实现方法：(1) 建栈这比较简单，只要建立一个一维数组，再把栈顶指针置为零。栈的容量根据具体的应用 要求而定。比如：type arraytype= array1. n of in teger;var stack:arraytype;top:i nteger;再在程序开始时，置top:=0 ;(2)

5、 测试栈测试栈顶指针的值，若top=0，则栈空；若top=n，则栈满。(3) 读栈若top=0 ,则栈空，无栈顶元素可读，出错；若top<>0 ,则回送栈顶元素的值STACKtop。(4) 进栈(push)将栈顶指针加1后，再把新元素送到栈顶。假设新元素x为整型，栈的最大深度为n,x和n设置为值型参。而栈和栈顶指针要设置成变量型参。procedure push(var stack:arraytype;var top:i nteger; n:i nteger;x:i nteger);beginif top=nthen begin writeln('Stack full! &#

6、39; ); halt endelse beg in top:=top+1; stacktop:= x enden d;(5) 退栈(pop)取得栈顶元素的值后，再把栈顶指针top减1。注意都用变量型参。procedure pop(var stack:arraytype;var top:i nteger;var x:i nteger);beginif top=0the n beg in write ln( Stack empty! ' ); halt endelse beg in x:=stacktop; top:=top-1 end en d;注意：由于栈本身和栈顶指针是密不可分的，

7、所以有时我们把他们定义成一个记录来处理。如：type stack=recordvec:array1. .n of in teger; n为栈可达到的最大深度 top:i nteger;en d;则以上几种运算的实现只要稍做修改即可。procedure push(var s:stack;x:i nteger);begin if s.top=n then begin writeln('Stack full! ' ); halt endelse beg in s.top:=s.top+1; s.vecs.top:= x enden d;procedure pop(var s:stac

8、k;var x:i nteger);beginif s.top=0the n beg in write ln( Stack empty! ' ); halt endelse beg in x:=s.vecs.top; s.top:=s.top-1 enden d;出栈有时也可用函数实现，如：fun cti on pop(var s:stack):i nteger;beginif s.top=0the n beg in write ln( Stack empty! ' ); halt endelse beg in pop:=s.vecs.top; s.top:=s.top-1 e

9、nd en d;栈的应用举例1、 若已知一个栈的入栈顺序是1, 2, 3,，n,其输出序列为 P1, P2, P3,，Pn,若P1 是 n,贝U Pi 是(C )。A)iB) n-1C)n-i+1D)不确定2、 以下哪一个不是栈的基本运算(B )。A)删除栈顶元素B)删除栈底的元素C)判断栈是否为空D)将栈置为空栈3、 设栈S和队列Q初始状态为空，元素 e 1 , e 2, e 3 , e 4, e 5, e 6依次通过栈S, 个元素出栈后即进入队列 Q,若出队的顺序为 e 2, e 4 , e 3 , e 6 , e 5 , e 1,则栈S 的容量至少应该为(B ) oA ) 2 B ) 3

10、 C ) 4 D ) 54、设栈S的初始状态为空，现有5个元素组成的序列1,2,3,4,5,对该序列在S栈上依次进行如下操作（从序列中的1开始，出栈后不在进栈）:进栈,进栈,进栈，出栈,进栈，出栈,进栈，问出栈的元素序列是：,栈顶指针的值为，栈顶元素为:。解答：出栈序列为3，4，栈顶指针值为3,栈顶元素为5。5、设栈S和队列Q初始状态为空，元素 e i，e 2， e 3，e 4，e 5，e 6依次通过栈S, 个元素出栈后即进入队列 Q,若出队顺序为 e 2，e 4，e 3，e 6，e 5，ei，则栈S的容 量至少应该为。解答：为3。6、如下图，有一个无穷大的的栈S,在栈的右边排列着 1,2,3

11、,4,5共五个车厢。其中每个车厢可以向左行走，也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢,请写出所有可能的到达出口的车厢排列总数（不必给出每种排列）。出口-S I解答：9栈的应用举例（栈与表达式）引言处理表达式是高级语言的编绎中的一个基本问题。它的实现是栈的一个重要应用，通过对处理表达式的讨论，可以帮助我们进一步了解栈的性能。内容讲授栈在计算机科学领域有着广泛的应用。比如在编译和运行计算机程序的过程中，就需要用栈进行语法检查（如检查begin和end、“（”和“）”等是否匹配）、计算表达式的值、实现过程和函数的递归调用等。下面举例说明栈在这些方面的应用。例1、假设一个表达

12、式有英文字母（小写）、运算符（+, , *, / ）和左右小（圆）括号构成，以“ 作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是 否匹配，若匹配，则返回“YES;否则返回“ NC”。表达式长度小于 255,左圆括号少于20个。分析：假设输入的字符串存储在c中（var c:string255）。我们可以定义一个栈：var s:array1.maxn of char;top:integer;用它来存放表达式中从左往右的左圆括号。算法的思路为：顺序（从左往右）扫描表达式的每个字符ci，若是“（”，则让它进栈；若遇到的是“)”则让栈顶元素出栈；当栈发生下溢或当表达式处理完毕而栈非空时,

13、表示不匹配，返回“ YES,否则表示匹配返回“NC”程序代码如下：var c:stri ng;function doit(c:stri ng):boolea n;var s:array1.2O of char;top,i:i nteger;ch:char;begintop:=0;i:=1;ch:=ci;while ch<> dobeginif (ch='(') or (ch=')') the n case ch of'(':begi n top:=top+1;stop:='(' end;')':if t

14、op>0 then top:=top-1else begi n doit:=false;exit end;en d;i:=i+1;ch:=ci;en d;if top=0 the n doit:=trueelse doit:=false;en d;beginassig n(i nput,'i n. txt');reset(i nput);readl n(c);writel n(doit(c);close(i nput);en d.补充关于表达式的三种表示法。1、中缀表达式：a+b2、后缀表达式：ab+3、前缀表达式：+ab4、中缀转后缀的方法及举例转换一般方法：把每个运算

15、符移到它的两个运算数后面，每个运算数后多加上一个空格(为了分隔各个运算数)，然后去掉所有括号即可。如：3/5+6 3 5 / 6 +表示空格，下同16-9* ( 4+3)19 9 4 3口 +*-2*(x+y)/(1-x)2 xD y +*1 x -/25 xD +aD aD b +*b +*（25+x）*（a*（a+b）+b）另外一种手工方法：可以用后面讲到的二叉表达式树结合先序、中序和后序遍历。5、中缀表达式的运算规则比较多，包括优先级、左右次序和括号；尤其是括号可以改 变优先顺序，这就只能在计算的每一步，用肉眼去扫描、观察和比较整个表达式中谁的优先级高，就先计算那部分。但用计算机去做就很

16、麻烦，而且效率不高。所以, 计算机科学中是把中缀表达式先转换成后缀表达式，在利用计算机来计算后缀表达式的值。后缀表达式又称"逆波兰式”，在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后顺序进行，整个计算过程仅需一遍扫描即可完成。6、两个任务：（1）把中缀表达式转换成后缀表达式；（2）求后缀表达式的值；例2、输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与 输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由+（加）、一（减）、X（乘）、/（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运 算符遵守

17、先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。以下是一个运行实例。输入：X+A* （Y-B） -Z/F输出：XAYB-*+ZF/-算法设计设置两个栈：操作数栈（OVS ）和运算符栈（ops）,用来分别存放表达式中的操作数和 运算符。开始时操作数栈为空，运算符栈 中放入一个特殊的标志运算符号 #号，并在 表达式的末尾加上一个 #号，并规定#号的 优先级最低，然后从左向右扫描表达式， 凡遇操作数便一律进栈；若遇运算符，则 判断其优先级是否大于运算符栈栈顶元素 的优先级。若小，则栈顶运算符退

18、栈，并 从操作数栈中弹出两个操作数（操作数为 后缀表达式）进行后缀变换处理，处理结 果进操作数栈，重复刚才的比较，直到栈 顶运算符的优先级大于等于当前运算符的 优先级，此时，若当前运算符的优先级大 于栈顶运算符的优先级，则当前运算符进 栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空， 操作数栈中只有一个元素，该元素就是所要求的后缀表达式。以下程序中的数组f用来存放运算符之间的优先级关系，1(>)表示前面的运算符优先于后面的运算符，-1(<)表示后面的运算符优先于前面的运算符，0(=)表示前面的运算符的优先级与后面的

19、运算符相同，2(ERR0R表示这两个运算符如果在扫描中相遇的话，意味着该表达式是错误的。需要补充的是：左括号的优先级是最高的，而里层的左括号比外层的左括号更优先，右括号的优先级是除 #号以外最低的，但左括号和右括号的优先级则是相等的，这 样定义的目的是为了消去括号。以上规律列表如下：、P2P1X+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=ERROR)&

20、gt;>>>ERROR>>#<<<<<ERROR=右上图是对范例上述算法还可用于求一个表达式的值和判断一个表达式是否有错等等。表达式的扫描示意图：程序清单program ex2(i nput,output);const max=100;op_set:set of char='+','-','*','/' letter:set of char='A'.'Z'var expressi on, result:stri ng;procedure s

21、ca n( expressi on: stri ng); var i,top1,top2:i nteger;ovs:array 1.max of strin gmax;ops:array 1.max of char; f:array'#'.7','#'.7' of shorti nt;beginf'+','*':=-1;f'+','/':=-1;f'+','(':=-1;f'-','*':=-1;f'-'

22、,'/':=-1;f'-','(':=-1;f'*','*':=1;f'*','/':=1;f'+','+':=1;f'+','-':=1;f'+',')':=1; f'+', #:=1;f'-','+':=1;f'-','-':=1;f'-',')':=1; f'-&#

23、39;,'#':=1;f'*','+':=1;f'*','-':=1;f'*','(':=-1; f'*',')':=1; f'*','#':=1;f'/','/':=1;f'(','/':=-1;f'#','/':=-1;f'/','+':=1;f'/','-'

24、:=1;f'/','*':=1;f7','(':=-1; f7',')':=1； f'/','#':=1;f'(','+':=-1;f'(','-':=-1;f'(','*':=-1;f'(','(':=-1; f'(',')':=0; f'(','#':=2;f')','

25、;+':=2;f') ','-':=2;f')','*':=2; f')', 7':=2; f')', '(':=2;f'',')'):=2; f'','#'):=2;f'#','+':=-1;f #,'-':=-1;f'#','*':=-1;f'#','('):=-1; f'#'

26、;,'':=2; f'#','#':=0;expressi on:=expressi on+'#'ops1:='#'top1:=0;top2:=1;for i:=1 to len gth(expressi on) dobeginif expressi on i in letterthe n begi n top1:=top1+1;ovstop1:=expressi on iendelse begi nwhile fopstop2,expressi on i=1 dobeginovstop1-1:=ovstop1-1

27、+ovstop1+opstop2;top1:=top1-1;top2:=top2-1en d;if fopstop2,expressi on i=0then top2:=top2-1else begi n top2:=top2+1; opstop2:=expressi on i en d;enden d;result:=ovs1en d;begi nma inwrite(' In put a expressi on:');readl n( expressi on);sca n( expressi on);write In ('The result is: ',r

28、esult)en d.测试输入：A*(X+Y)/(B-Z)输出：AXY+*BZ-/例3、编程求一个后缀表达式的值。从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（一）、乘（* ）、除（/）四种运算符。每个运算数之间用一个空格 隔开，不需要判断给你的表达式是否合法。分析：先读入后缀表达式（字符串）。后缀表达式的处理过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。程序：const maxn=20;var stack:array1.

29、max n of in teger;s:stri ng;function comp（s:stri ng）:i nteger;var ch:char;i,top,x,y,z:i nteger;begintop:=0;i:=1;ch:=si;while i<=le ngth（s） do begi ncase ch of'0'.'9':begi n x:=0;while ch<>' ' do beg inx:=x*10+ord（ch）-ord（'0'）;i:=i+1; ch:=si;en d;top:=top+1; s

30、tacktop:=x;en d;'+':begi nx:=stacktop;top:=top-1;y:=stacktop;z:=y+x;stacktop:=z end;'-':begi nx:=stacktop;top:=top-1;y:=stacktop;z:=y-x;stacktop:=z end;'*':beginx:=stacktop;top:=top-1;y:=stacktop;z:=y*x;stacktop:=z end;T:begi n x:=stacktop;top:=top-1;y:=stacktop;z:=ydivx;stac

31、ktop:=z end;en d;i:=i+1;ch:=si;en d;whilecomp:=stacktop;end;begi nma inwrite In (' in put a stri ng(_over):');readl n(s);write In ('result= ',comp(s);readl n;en d.作业与思考请把本节的内容组合在一起， 编一个程序，输入一个中缀表达式（由0-9组成的运算数、 加+减一乘*除/四种运算符、左右小括号组成。注意“一”也可作为负数的标志，表达式以“作为结束符），判断表达式是否合法，如果不合法，请输出“NO;否则

32、请把表达式转换成后缀形式，再求出后缀表达式的值并输出。注意：必须用栈操作，不能直接输出表达式的值。如果再考虑是实数运算呢？栈与递归递归算法及在计算机中的实现1、递归算法例1、用递归算法把任一给定的十进制正整数(<=32000)转换成八进制数输出，程序如下:var m:i nteger;procedure tran(n:integer); 递归过程var k:i nteger;begink:=n mod 8;n:=n div 8;if n<>0 the n tran(n);write(k:1)en d;begin 主程序write(' in put m:');r

33、eadl n( m);write(m,'=(');tran (m);writel n( ')8');readl n;en d.输入：m=765下划线表示输入输出：765= (1375) 8例2、用递归算法求 N阶乘(N =1*2*3*N,N<20);var n:i nteger;function f(n:integer):longint; 递归函数，N=20 时，超过 maxlongintbeginif n=0 then f:=1else f:=n*f(n-1)en d;begin 主程序write(' in put n:');readl

34、n(n);write( n,'!=',f( n);en d.2、递归在计算机中的实现计算机执行递归算法时，是通过栈来实现的。 具体说来，就是在（递归过程或递归函数）开始运行时，系统首先为递归建立一个栈，该栈的元素类型（数据域）包括值参、局部变量 和返回地址；在每次执行递归调用语句时之前，自动把本算法中所使用的值参和局部变量的当前值以及调用后的返回地址压栈（一般形象地称为“保存现场”，以便需要时“恢复现场”返回到某一状态），在每次递归调用结束后，又自动把栈顶元素（各个域）的值分别赋给相 应的值参和局部变量（出栈），以便使它们恢复到调用前的值，接着无条件转向（返回）由 返回地址所指

35、定的位置继续执行算法。具体到上面的例1中，当遇到递归调用tran（n）时，系统首先为后面的递归调用建立一 个含有3个域（值参n,局部变量k和一个返回地址）的栈；在每次执行递归调用tran（n）前，系统自动把 n和k的当前值以及 write（k:1） 语句的开始位置（即调用结束后的返回地 址）压栈；在每次执行到最后的end语句（即一次递归调用结束）后，又自动把栈顶的与n和k对应的值分别赋给 n和k （出栈），接着无条件转向 write（k:1） 语句的开始位置继续向 下执行程序。3、递归的缺点早期操作系统 DOS勺内核是限制只能使用 640K内存（当时的机器内存也很小），在此之 上的BP运行时，

36、可用的所有内存空间最大也只能为640K,其中程序代码、常量、变量和堆栈（局部变量、子程序参数、返回地址；即递归中的栈）各占64K,在BP中的OPTIONS菜单的MEMORY SIZ子菜单中可以修改 STACK SIZE至多到64K （一般设置为 65520）,可以解 决很多递归程序遇到的栈溢出错误。但有时还是不够，这时就想用640K以内（64K以上）的多余空间，方法是手工开辟一个栈空间模拟系统处理递归的实现方法，这样就可以把一个递归过程转换成非递归过程，一方面可以进一步加深对栈和递归的理解，另一方面也可以解决一些递归无法解决的问题。带来的问题是程序会很复杂。递归转换为非递归设P是一个递归算法，

37、假定P中共有m个值参和局部变量，共有t处递归调用P的语句, 则把P改写成一个非递归算法的一般规则为：1、定义一个栈S,用来保存每次递归调用前值参和局部变量的当前值以及调用后的返回地址。即S应该含有m+1个域，且S的深度必须足够大，使得递归过程中不会发生栈溢出。2、 定义t+2个语句标号，其中用一个标号标在原算法中的第一条语句上，用另一个标号标 在作返回处理的第一条语句上 ，其余t个标号标在t处递归调用的返回地址，分别标在 相应的语句上。3、把每一个递归调用语句改写成如下形式：（1）把值参和局部变量的当前值以及调用后的返回地址压入栈；（2）把值参所对应的实在参数表达式的值赋给值参变量；（3）无条

38、件转向原算法的第一条语句；4、在算法结束前增加返回处理，当栈非空时做：（1）出栈；（2）把原栈顶中前 m个域的值分别赋给各对应的值参和局部变量；（3）无条件转向由本次返回地址所指定的位置；5、增设一个同S栈的成分类型（元素）相同的变量，作为进出栈的缓冲变量，对于递归函 数，还需要再增设一个保存函数值中间结果的临时变量，用这个变量替换函数体中的所 有函数名，待函数结束之前，在把这个变量的值赋给函数名返回。6、在原算法的第一条语句之前，增加一条把栈置空的语句。7、 对于递归函数而言，若某条赋值语句中包含两处或多处递归调用（假设为n处），则应首先把它拆成n条赋值语句，使得每条赋值语句只包含一处递归调

39、用，同时对增加的n-1条赋值语句，要增设 n-1个局部变量，然后按以上六条规则转换成非递归函数。应用举例例3、 把例1中的递归过程改写成非递归过程。procedure tran(n:integer); 非递归过程label 1,2,3;因为只有1处递归调用，所以定义 t+2=3个标号type no de=record 定义栈的成分类型，因为值参和局部变量共2个，所以m+1=3个域页脚n:integer; k:integer; r:integer; en d; stack=record en d;var s:stack; x:no de; k:integer; vec:array1.7 of n

40、ode; 32000top:integer; 栈顶指针值参n的域局部变量k的域返回地址的域定义一个栈类型，包括数据域（一个数组）和一个栈顶指针域以内的十进制正整数转换成八进制数，不会 超过七位数，数组元素类型为n ode类型定义栈变量 进出栈的缓冲变量 原来的局部变量procedure push(var s:stack;x:node); 进栈过程，注意 s 一定要定义成变量型参数begin因为栈的变化要带出过程if s.top=7 the n begi n write('up-overflow');exit;e ndelse begi n s.top:=s.top+1;s.ve

41、cs.top:=x;e nd;en d;procedure pop(var s:stack;var x:n ode); 出栈过程，都要定义成变量型参。一方面出栈的元素存放在x中要带出过程，另外栈顶指针也变化了，所以 s也要定义成变量型参beginif s.top=0 the n begi n write('dow n-o verflow');exit;e ndelse begi n x:=s.vecs.top;s.top:=s.top-1;e nd;en d;begins.top:=0;按照第6条1:k:=n mod 8; 按照第2条的红色语句n:=n div 8;if n&l

42、t;>0 the n begi n 按照第3条，3个步骤，本题不需要第x. n:=n;x.k:=k;x.r:=2;push(s,x); （1）goto 1;（3）en d;2:write(k:1);按照第2条的蓝色语句3:if s.top>0 the n begi n 按照第4条，3个步骤pop(s,x); （1）n :=x .n;k:=x.k;（2）goto 2;（3）2）小句en d;en d;建议：单步跟踪各个变量，观察理解过程例4、把例2中的递归函数改写成非递归函数 function f（n:integer）:longint; 非递归函数label 1,2,3;var s:

43、array1.20 of integer;栈，必须大于等于n,保证不溢出top:i nteger; f1:lo ngint; begintop:=0;1:if n=0 the n begi n f1:=栈顶保存中间结果的临时变量栈的初始化=1;goto 3;e nd 遇到边界就结束转返回处理 else beg in top:=top+1; 否则，进栈atop:=n;n:=n-1;实参减 1goto 1;转向开始，继续en d;2:f1:=n*f1;根据 n 和 f(n-1),求 f(n)3:if top>0 then begin n:=atop;做返回处理top:=top-1;goto

44、2;转向返回地址en d;f:=f1; 赋值en d;1、上面的程序其实已经进行了简化，一是栈只设置了一个保存值参n的域，二是忽略了缓冲变量，而直接用n,三是省略了返回地址，因为每个递归调用的返回地址都相同；2、以上算法中，从标号 1到goto 1所构成的循环，实际上是一个递推过程；从 n 推到0为止；从标号2到goto 2所构成的循环是一个回代过程；3、假设n=5，请大家画出栈的变化情况。小结思考从以上可以看出，递归算法简单直观，是整个计算机算法和程序设计领域一个非常重要 的方面，必须熟练掌握和应用它。但计算机的执行过程比较复杂，需要用系统栈进行频繁的进出栈操作和转移操作。递归转化为非递归后，可以解决一些空间上不够的问题，但程序太复杂。所以，并不是一切递归问题都要设计成非递归算法。实际上，很多稍微复杂一点的问 题(比如：二叉树的遍历、图的遍历、快速排序等)，不仅很难写出它们的非递归过程，而且即使写出来也非常累赘和难懂。在这种情况下，编写出递归算法是最佳选择，有时比较简单的递归算法也可以用迭代加循环或栈加循环的方法去实现。如：function f(n: